Driftsort to prosty sposób na „sortowanie” tablicy. Działa poprzez „przesuwanie” lub „obracanie” elementów w tablicy, dopóki tablica nie zostanie posortowana lub dopóki tablica nie zostanie posortowana.

Przejrzyjmy dwa przykłady. Najpierw rozważ tablicę [10, 2, 3, 4, 7]. Ponieważ tablica nie jest posortowana, obracamy ją raz. (Może się to zdarzyć w dowolnym kierunku, pod warunkiem, że pozostaje ten sam kierunek.) Następnie tablica staje się:

[7, 10, 2, 3, 4]

To nie jest posortowane, więc obracamy ponownie.

[4, 7, 10, 2, 3]

I jeszcze raz:

[3, 4, 7, 10, 2]

I ostatni raz:

[2, 3, 4, 7, 10]

I to jest posortowane! Tak więc tablica [10, 2, 3, 4, 7]jest przenośna. Oto wszystkie obroty tablicy, dla przejrzystości:

[10, 2, 3, 4, 7]
[7, 10, 2, 3, 4]
[4, 7, 10, 2, 3]
[3, 4, 7, 10, 2]
[2, 3, 4, 7, 10]

Rozważ teraz tablicę [5, 3, 9, 2, 6, 7]. Spójrz na jego obroty:

[5, 3, 9, 2, 6, 7]
[7, 5, 3, 9, 2, 6]
[6, 7, 5, 3, 9, 2]
[2, 6, 7, 5, 3, 9]
[9, 2, 6, 7, 5, 3]
[3, 9, 2, 6, 7, 5]

Żadna z tych tablic nie jest sortowana, więc tablicy [5, 3, 9, 2, 6, 7]nie można przenosić.

Cel Biorąc pod uwagę niepustą tablicę / listę liczb całkowitych jako dane wejściowe do programu / funkcji, zaimplementuj driftsort na wejściu i wyślij go, lub wypisz wartość falsey ( lub pustą tablicę / listę), jeśli nie można go posortować. Liczby całkowite są przypisane do twoich języków max / min, ale musi to być co najmniej 255 dla maksimum i 0 dla min.

Możesz użyć wbudowanych metod sortowania, ale nie wbudowanego, który rozwiązuje problem.

To jest golf golfowy , więc najkrótszy program w bajtach.

Przypadki testowe

input => output
[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]

Galaretka , 6 bajtów

ṙỤċṢȧṢ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

ṙỤċṢȧṢ  Main link. Argument: A (list)

 Ụ      Grade up; return the indices of A, sorted by their corresponding values.
ṛ       Rotate A by each index, yielding the list of all rotations.
   Ṣ    Yield A, sorted.
  ċ     Count the number of times sorted(A) appears in the rotations.
        This gives 0 if the list isn't driftsortable.
    ȧṢ  Logical AND with sorted(A); replaces a positive count with the sorted list.

Ruby, 33

->a{a.any?{a.sort==a.rotate!}&&a}

a.any?odpala jeden raz dla każdego elementu w tablicy, z wyjątkiem tego, że zatrzymuje się (i zwraca wartość true), gdy tylko tablica zostanie zmutowana w posortowany stan. Jeśli tak się stanie, zwracamy zmutowaną tablicę. W przeciwnym razie zwracamy zwracaną wartość false any?.

Python 2, 51 bajtów

lambda l:sorted(l)*(map(cmp,l[-1:]+l,l).count(1)<3)

Nie przeszkadza w obracaniu. Zamiast tego sortuje listę, a następnie sprawdza, czy oryginał można posortować dryfując, sprawdzając, czy występuje co najmniej jeden spadek między kolejnymi elementami cyklicznej listy. Liczy się, <3ponieważ uzupełnia mapkrótszą listę Nonena końcu, dodając fałszywy spadek.

Pyth, 9 bajtów

*SQ}SQ.:+

Wyjaśnienie:

           - Q = eval(input())
         + -    Q+Q
       .:  -   sublists(^)
   }       -  V in ^
    SQ     -   sorted(Q)
*SQ        - ^ * sorted(Q) (return sorted(Q) if ^ True)

Wypróbuj tutaj!

Lub użyj pakietu testowego!

Matlab, 61 47 41 bajtów

Dzięki @Suever za -6 bajtów!

@(a)sort(a)+0*min(strfind([a,a],sort(a)))

Jeśli strfind([a,a],sort(a))spróbuje znaleźć posortowany wektor wejściowy jako „podłańcuch” nieposortowanego, zostanie on dołączony do siebie. Jeśli to prawda, dane wejściowe można przenosić i otrzymujemy wektor o długości 2, jeśli nie, otrzymujemy pusty wektor. minpo prostu przekształca to w wektor liczbowy / pusty. Dodanie posortowanego wektora do 0 po prostu wyświetla go, dodanie go do pustego wektora powoduje błąd.

Julia, 71 66 52 bajtów

x->(y=sort(x))∈[circshift(x,i)for i=1:endof(x)]&&y

Jest to anonimowa funkcja, która przyjmuje tablicę i zwraca tablicę lub wartość logiczną. Aby go wywołać, przypisz go do zmiennej.

Dla tablicy wejściowej x tworzymy zestaw wszystkich obrotów x i sprawdzamy, czy posortowana wersja x jest elementem tej listy. Jeśli tak, zwracamy x posortowane, w przeciwnym razie zwracamy fałsz.

Zaoszczędź 19 bajtów dzięki Dennis!

Pip , 15 + 1 = 17 16 bajtów

Ugh, inne języki gry w golfa wydmuchują to z wody. Jednak skoro już to napisałem ...

L#gI$<gPBPOgYgy

Pobiera dane wejściowe jako rozdzielone spacjami argumenty wiersza polecenia. Wymaga -plub innej flagi formatującej tablicę, aby wyświetlać wynik czytelnie, a nie konkatenowany. Fałszywy przypadek wyświetla pusty ciąg znaków, który jest widoczny dzięki końcowemu znakowi nowej linii.

                 Implicit: g is array of cmdline args; y is empty string
L#g              Loop len(g) times:
         POg       Pop the first item from g
      gPB          Push it onto the back of g
    $<             Fold on < (true if g is now sorted)
   I        Yg     If true, yank g into y
              y  Autoprint y

JavaScript (ES6), 72 70 65 bajtów

a=>a.map(y=>{c+=x>y;x=y},x=a.slice(c=-1))|c<1&&a.sort((a,b)=>a-b)

Zwraca 0w przypadku awarii. Poprzednia 85 83 80-bajtowa wersja unikała wywoływania sort:

a=>a.map((y,i)=>{x>y&&(c++,j=i);x=y},x=a.slice(c=-1))|c<1&&a.splice(j).concat(a)

Edycja: Zapisano 2 bajty, inicjując cna -1zamiast 0. Zapisane 5 bajtów poprzez przełączenie od reducecelu map, ech ...

05AB1E , 12 bajtów

Kod:

DgFÀÐ{Qi,}}0

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Snowman 1.0.2 , 27 bajtów

((}#AsO|##aC,as|aLNdE`aR*))

Jest to podprogram, który pobiera dane wejściowe i wyjściowe do bieżącego permawaru.

Wypróbuj online!

((                       ))  subroutine
  }                          set our active variables b, e, and g:
                              .[a] *[b] .[c]
                              .[d]      *[e]    (* represents an active variable)
                              .[f] *[g] .[h]
   #                         store the input in variable b
    AsO                      sort in-place
       |                     swap b with g; now sorted input is in g
        ##                   store the input again in b and e
          aC                 concat; now the input doubled is in b and e is empty
            ,                swap e/g; now b has 2*input and e has sorted input
             as              split 2*input on sort(input) and store result in g
               |             bring the result up to b (we no longer care about g)
                aLNdE        take length and decrement; now we have 0 in b if the
                               array is not driftsortable and 1 if it is
                     `aR     repeat e (the sorted array) b times:
                               if b is 0 (nondriftsortable), returns [] (falsy)
                               otherwise (b=1), returns sorted array unchanged
                        *    put this back into the permavar

MATL, 13 12 10 9 bajtów

SGthyXfa*

Ten sam pomysł, co odpowiedź @ flawr, w której przechwytujemy strfind( Xf), aby znaleźć posortowaną wersję danych wejściowych w ramach konkatenacji dwóch kopii danych wejściowych.

Wypróbuj online!

Wyjaśnienie

        % Implicitly get input
S       % Sort the input
Gth     % Explicitly grab the input again and concatenate with itself
y       % Copy the sorted version from the bottom of the stack
Xf      % Look for the sorted version as a subset
a       % Gives a 1 if there were matches and 0 otherwise
*       % Multiply by the sorted array. Yields all zeros for no match and the
        % sorted array when a match was found
        % Implicitly display the stack contents

Julia, 33 bajty

x->sum(diff([x;x]).<0)<3&&sort(x)

Wypróbuj online!

Jak to działa

To konkatenuje tablicę x z samym sobą i zlicza liczbę par, które są nieuporządkowane, tj. Liczbę sąsiadujących podrzędnych [a, b], dla których b - a <0 . Jeśli c jest liczbą nieuporządkowanych par samego x , a t wynosi 1, jeśli ostatni element x jest większy niż jego pierwszy, sumzwróci 2c + t .

Tablica x nadaje się do dryfowania iff (c, t) = (1, 0) ( x należy obrócić do mniejszej wartości jedynej nieuporządkowanej pary), (c, t) = (0, 1) ( x jest sortowane) lub (c, t) = (0, 0) ( x jest posortowane, a wszystkie jego elementy są równe), co jest prawdą, jeśli iff 2c + t <3 .

JavaScript ES6, 48 45 43 znaków

x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x

Test:

f=x=>~(x+[,x]).indexOf(x.sort((a,b)=>a-b))&&x
;`[1] => [1]
[5, 0, 5] => [0, 5, 5]
[3, 2, 1] => false
[0, 9, 3] => false
[1, 2, 3, 4] => [1, 2, 3, 4]
[4, 1, 2, 3] => [1, 2, 3, 4]
[0, 2, 0, 2] => false
[5, 3, 9, 2, 6, 7] => false
[0, 0, 0, 0, 0, 0, 0] => [0, 0, 0, 0, 0, 0, 0]
[75, 230, 30, 42, 50] => [30, 42, 50, 75, 230]
[255, 255, 200, 200, 203] => [200, 200, 203, 255, 255]`
.split`
`.map(t => t.replace(/^(.*) => (.*)$/, "f($1)+'' == $2")).every(eval)

Brachylog , 39 bajtów

l:0re:?{[0:L],!L.|rh$(L,?h-1=:L:1&.}.o.

Naprawdę muszę dodać opcjonalny argument, aby $( - circular permute leftpermutować więcej niż raz ... To byłoby 13 bajtów. Poczeka to po wdrożeniu nowego stabilnego transpilera w Prologu.

Wyjaśnienie

l:0re                                     I = a number between 0 and the length of Input
     :?{[0:L],!L.|rh$(L,?h-1=:L:1&.}      All this mess is simply circular permutating the
                                          input I times
                                    .o.   Unify the Output with that circular permutation
                                          if it is sorted, else try another value of I

Ruby, 47 bajtów

Funkcja rekurencyjna. Zwraca, niljeśli tablica wejściowa nie może być dzielona.

f=->a,i=0{a.sort==a ?a:a[i+=1]?f[a.rotate,i]:p}

CJam, 17 lat 13 bajtów

Dzięki Dennis za oszczędność 4 bajtów.

{_$\_+1$#)g*}

Nienazwany blok (funkcja), który pobiera i zwraca listę.

Zestaw testowy.

Wyjaśnienie

Zasadniczo wykorzystuje to obserwację xnor, że posortowana lista pojawia się dwukrotnie na liście oryginalnej, jeśli można ją posortować:

_$   e# Duplicate input and sort.
\_+  e# Get other copy and append to itself.
1$   e# Copy sorted list.
#    e# Find first position of sorted list in twice the original,
     e# of -1 if it's not found.
)g   e# Increment and take signum to map to 0 or 1.
*    e# Repeat sorted array that many times to turn it into an empty
     e# array if the input was not drift sortable.

C ++ 14, 242 znaków

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}}

Jeśli nie mogę pozostawić pustego wyjścia, 252 znaków http://ideone.com/HAzJ5V

#include<iostream>
#include<vector>
#include<algorithm>
#define b v.begin()
using namespace std;int main(){vector<int>v;int x,n=0;for(;cin>>x;++n)v.push_back(x);for(x=n;x--;rotate(b,b+1,b+n))if(is_sorted(b,b+n)){for(x:v)cout<<x<<' ';return 0;}cout<<'-';}

Wersja bez golfa http://ideone.com/Dsbs8W

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define b v.begin()

int main()
{
  vector <int> v;
  int x, n=0;

  for(;cin>>x;++n)
    v.push_back(x);

  for(x=n;x--;rotate(b,b+1,b+n))
    if(is_sorted(b,b+n))
    {
      for(x:v) cout<<x<<' ';
      return 0;
    }

  cout << '-';
}

PS: W oparciu o pomysł @ MichelfrancisBustillos .

Java 7, 207 bajtów

int[]D(int[]i){int x,z;z=x=-1;int[]d=new int[i.length];while(++x<i.length)if(i[x]>i[(x+1)%i.length])if(z<0)z=(x+1)%i.length;else return null;if(z<0)z=0;x=-1;while(++x<d.length)d[x]=i[z++%i.length];return d;}

Szczegółowe spróbuj tutaj

// driftsort in ascending-order
int[] D(int[]i)
{
    int x = -1,z = -1;
    int[] d = new int[i.length];

    while ((++x) < i.length)
    {
        if (i[x] > i[(x+1)%i.length])
        {
            if(z < 0) z = (x+1)%i.length;
            else return null; // not driftsortable
        }
    }

    if(z < 0) z = 0;
    x = -1;
    while ((++x) < d.length)
    {
        d[x] = i[(z++)%i.length];
    }

    return d;
}

Java 175

wypisuje dane wyjściowe jako wartości oddzielone spacjami lub drukuje fdla wartości falsey.

void d(int[]a){String s;for(int v,w,x=-1,y,z=a.length;++x<z;){v=a[x];s=""+v;for(y=0;++y<z;v=w){w=a[(x+y)%z];if(v>w){s="f";break;}s+=" "+w;}if(y==z)break;}System.out.print(s);}

przechodzi przez wszystkie kombinacje tablicy liczb całkowitych, aż znajdzie prawidłową sekwencję lub zabraknie kombinacji. tablica nie jest modyfikowana, ale zamiast tego posortowana sekwencja jest przechowywana jako ciąg rozdzielany spacjami.

nieco bardziej czytelny:

void driftsort(int[]array){
    String str;
    for(int previous,current,x=-1,y,len=array.length;++x<len;){
        previous=array[x];
        s=""+previous;
        for(y=0;++y<len;previous=current){
            current=array[(y+x)%len];
            if(previous>current){
                str="false";
                break;
            }
            str+=" "+current;
        }
        if(y==len)break;
    }
    System.out.print(str);
}

spróbuj online

C, 105 bajtów

i,s;main(c,v)char**v;{c--;while(i++<c)if(atoi(v[i])>atoi(v[i%c+1]))c*=!s,s=i;while(--i)puts(v[s++%c+1]);}

Akceptuje to wejściowe liczby całkowite jako osobne argumenty wiersza poleceń i drukuje listę wyników jako jedną liczbę całkowitą w wierszu.

Jeśli listy nie można przenosić, program kończy pracę przedwcześnie z powodu wyjątku zmiennoprzecinkowego, więc jego puste dane wyjściowe reprezentują pustą listę.

Weryfikacja

$ gcc -o driftsort driftsort.c 2>&-
$ ./driftsort 1 | cat
1
$ ./driftsort 5 0 5 | cat
0
5
5
$ ./driftsort 3 2 1 | cat
$ ./driftsort 0 9 3 | cat
$ ./driftsort 1 2 3 4 | cat
1
2
3
4
$ ./driftsort 4 1 2 3 | cat
1
2
3
4
$ ./driftsort 0 2 0 2 | cat
$ ./driftsort 5 3 9 2 6 7 | cat
$ ./driftsort 0 0 0 0 0 0 0 | cat
0
0
0
0
0
0
0
$ ./driftsort 75 230 30 42 50 | cat
30
42
50
75
230
$ ./driftsort 255 255 200 200 203 | cat
200
200
203
255
255

Ruby, 28 lat

->a{(a*2*?,)[a.sort!*?,]&&a}

Zwraca albo posortowaną tablicę, albo nil(co jest wartością falsy), jeśli danych wejściowych nie można posortować.

Python, 53 bajty

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))

Jeśli chcesz przetestować to, przejdź na https://www.repl.it/languages/python3 i skopiuj to:

s,N=sorted,lambda x:s(x)*(str(s(x))[1:-1]in str(x+x))
print(N([1,2,3,4,5,0]))

Jak to działa:

• sto zmienna przechowująca funkcję sortedpythona, która sortuje listy
• N jest główną funkcją
• s(x)Posortowana lista wejściowa: jest mnożona przez to, czy lista jest dostępna do driftustr(s(x))[1:-1]in str(x+x) do driftu (dzięki @xnor)
  • Działa to, ponieważ [1,2,3,4]*false powoduje powstanie pustej listy[]
  • i [1,2,3,4]*truewyniki w[1,2,3,4]

Python, 83 bajty

def f(l):g=sorted(l);return g if any(l[x:]+l[:x]==g for x in range(len(l)))else 1>2

Zawstydzają to inne odpowiedzi pytona, ale i tak mogę to opublikować. Naprawdę nie lubię

range(len(l)))

część. Czy istnieje szybszy sposób na iterację po liście?

MATLAB / Octave, 118 bajtów

function r(a)
i=0
while (~issorted(a) && i<length(a))
    a=a([2:end 1]),i=i+1
end
if issorted(a)
    a
else
    0
end

PowerShell v2 +, 87 80 bajtów

param($a)0..($a.length-1)|%{if($a[$_-1]-gt$a[$_]){$c--}};(0,($a|sort))[++$c-ge0]

Przechodzi przez listę wprowadzania $a, sprawdzając każdy element parami (w tym ostatni i pierwszy), aby sprawdzić, czy istnieje więcej niż jedna para malejąca. Jeśli konkretna para maleje, zmniejszamy $c. Zwraca posortowaną listę lub pojedynczy element 0na podstawie wartości $cna końcu. Jeśli występuje więcej niż jedna „zła” para, to ++$cnadal będzie ona ujemna, w przeciwnym razie będzie co najmniej 0, więc wybierany jest drugi element pseudo-trójki ($a|sort ).

Widzę, że Xnor zrobił coś podobnego , ale wymyśliłem to niezależnie.

Współczynnik, 47 bajtów

[ dup dup append [ natural-sort ] dip subseq? ]

połącz sekwencję z sobą, a następnie sprawdź, czy posortowane tłumaczenie oryginału jest podsekwencją.

C ++, 313 359 370 bajtów

Ogromne pozdrowienia dla @Qwertiy za to, że działał i nauczył mnie kilku świetnych metod gry w golfa!

Gra w golfa:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){vector<int> v;int x,c=0,s=0,y;while(cin>>x)v.push_back(x);do if(rotate(v.begin(),v.begin()+1,v.end()),c++,is_sorted(v.begin(),v.end()))s=1;while(!s&c<=v.size());if(s)for(y=0;y<v.size();y++)cout<<v[y]<<" ";else cout<<"False";}

Nie golfowany:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  vector <int> v;
  int x, c=0, s=0, y;

  while(cin>>x)
    v.push_back(x);

  do 
    if (
      rotate(v.begin(),v.begin()+1,v.end()),
      c++,
      is_sorted(v.begin(),v.end())
    ) s = 1;
  while(!s & c <= v.size());

  if (s)
    for(y=0; y<v.size(); y++)
      cout<<v[y]<<" ";
  else
    cout<<"False";
}

Mathcad, TBD

W Mathcad 0 (skalar) == false.

(Równoważna) liczba bajtów to TBD, dopóki nie zostanie uzgodniona metoda liczenia. Około 52 bajtów przy użyciu równoważnika bajt = operator / symbol.

Mathematica 55 50 61 58 bajtów

Z 3 bajtami zaoszczędzonymi dzięki Martinowi Büttnerowi.

Moje wcześniejsze próby nie przeszły wszystkich przypadków testowych. Musiałem dodać, Unionaby uniknąć powtórzeń na liście, które były wprowadzane w kolejności.

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&

Testy

Join@Union@Cases[NestList[RotateRight,#,Length@#],Sort@#]&/@
{{1},{5,0,5},{3,2,1},{0,9,3},{1,2,3,4},{4,1,2,3},{0,2,0,2},{5,3,9,2,6,7},
{0,0,0,0,0,0,0},{75,230,30,42,50},{255,255,200,200,203}}

{{1}, {0, 5, 5}, {}, {}, {1, 2, 3, 4}, {1, 2, 3, 4}, {}, {}, {0, 0, 0, 0, 0, 0, 0}, {30, 42, 50, 75, 230}, {200, 200, 203, 255, 255}}

Wyjaśnienie

Obróć listę wejściową w prawo od 1 do nrazy, gdzie njest długość listy wejściowej. Jeśli posortowana lista wejściowa znajduje się wśród wyjściowych list obróconych, zwróć ją; w przeciwnym razie zwróć pustą listę.

PHP, 98 bajtów

Wyprowadza, 1jeśli można dryfować, w przeciwnym razie nic

$a=$argv[1];$b=$a;sort($a);foreach($a as $v){echo($a===$b?1:'');array_unshift($b, array_pop($b));}