Driftsort ist eine einfache Möglichkeit, ein Array zu "sortieren". Es funktioniert, indem die Elemente im Array "verschoben" oder "gedreht" werden, bis das Array sortiert ist oder bis das Array nicht mehr sortiert werden kann.

Lassen Sie uns zwei Beispiele durchgehen. Betrachten Sie zunächst das Array [10, 2, 3, 4, 7]. Da das Array nicht sortiert ist, drehen wir es einmal. (Dies kann in beide Richtungen geschehen, solange die Richtung gleich bleibt.) Dann wird das Array:

[7, 10, 2, 3, 4]

Dies ist nicht sortiert, so dass wir erneut drehen.

[4, 7, 10, 2, 3]

Und wieder:

[3, 4, 7, 10, 2]

Und ein letztes Mal:

[2, 3, 4, 7, 10]

Und es ist sortiert! Das Array [10, 2, 3, 4, 7]ist also driftsortierbar. Hier sind zur Verdeutlichung alle Rotationen des Arrays:

[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]

Betrachten Sie nun das Array [5, 3, 9, 2, 6, 7]. Schauen Sie sich die Rotationen an:

[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]

Keines dieser Arrays ist sortiert, sodass das Array [5, 3, 9, 2, 6, 7]nicht driftsortierbar ist.

Zielsetzung Wenn ein nicht leeres Array / eine Liste von Ganzzahlen als Eingabe für ein Programm / eine Funktion verwendet wird, implementieren Sie eine Driftsortierung für die Eingabe und geben Sie sie aus, oder geben Sie einen Falsey - Wert aus ( oder ein leeres Array / eine leere Liste) aus, wenn keine Driftsortierung möglich ist. Die Ganzzahlen sind an Ihre Sprachen max / min gebunden, aber dies muss mindestens 255 für das Maximum und 0 für das Minimum sein.

Sie können integrierte Sortiermethoden verwenden, jedoch keine integrierten, die die Herausforderung lösen.

Dies ist ein Code-Golf , also das kürzeste Programm in Bytes.

Testfälle

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]

Gelee , 6 Bytes

ṙỤċṢȧṢ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

ṙỤċṢȧṢ  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?Feuert bis zu einmal für jedes Element im Array ab, außer es stoppt (und gibt true zurück), sobald das Array in einen sortierten Zustand geändert wurde. In diesem Fall geben wir das mutierte Array zurück. Andernfalls geben wir den zurückgegebenen falschen Wert any?zurück.

Python 2, 51 Bytes

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

Rotiert nicht. Sortiert stattdessen die Liste und prüft, ob das Original driftsortierbar ist, indem überprüft wird, ob höchstens eine Abnahme unter aufeinanderfolgenden Elementen der zyklisierten Liste vorliegt. Die Zählung erfolgt, <3weil mapdie kürzere Liste mit Noneam Ende aufgefüllt wird und eine falsche Abnahme hinzugefügt wird.

Pyth, 9 Bytes

*SQ}SQ.:+

Erläuterung:

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

Probieren Sie es hier aus!

Oder benutze eine Testsuite!

Matlab, 61 47 41 Bytes

Danke @Suever für -6 Bytes!

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

Wenn strfind([a,a],sort(a))versucht wird, den sortierten Eingabevektor als 'Teilzeichenfolge' der unsortierten zu finden, wurde dieser an sich selbst angehängt. Wenn wahr, ist die Eingabe driftsortierbar und wir erhalten einen Vektor der Länge 2, wenn nicht, erhalten wir einen leeren Vektor. mintransformiert dies einfach in eine Zahl / einen leeren Vektor. Wenn Sie den sortierten Vektor zu 0 hinzufügen, wird er nur angezeigt, und wenn Sie ihn einem leeren Vektor hinzufügen, wird ein Fehler ausgegeben.

Julia, 71 66 52 Bytes

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

Dies ist eine anonyme Funktion, die ein Array akzeptiert und ein Array oder einen Booleschen Wert zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Für ein Eingabearray x erstellen wir die Menge aller Rotationen von x und prüfen, ob die sortierte Version x ein Element dieser Liste ist. Wenn dies der Fall ist, geben wir x sortiert zurück, andernfalls geben wir false zurück.

19 Bytes gespart dank Dennis!

Pip , 15 + 1 = 17 - 16 Bytes

Puh, die anderen Golfsprachen blasen das aus dem Wasser. Da ich es aber schon geschrieben habe ...

L#gI$<gPBPOgYgy

Nimmt Eingaben als durch Leerzeichen getrennte Befehlszeilenargumente an. Benötigt -poder ein anderes Array-Formatierungs-Flag, um das Ergebnis leserlich und nicht verkettet anzuzeigen. Der falsche Fall gibt eine leere Zeichenfolge aus, die anhand der nachgestellten Zeilenumbrüche sichtbar ist.

                 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 Bytes

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

Kehrt 0bei einem Fehler zurück. Vorherige 85 83 80-Byte-Version verhinderte den Aufruf von 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)

Bearbeiten: 2 Bytes durch Initialisieren cauf -1anstelle von gespeichert 0. 5 Bytes gespart durch Umschalten von reduceauf map, seufz ...

05AB1E , 12 Bytes

Code:

DgFÀÐ{Qi,}}0

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Schneemann 1.0.2 , 27 Bytes

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

Dies ist eine Unterroutine, die Eingaben von und Ausgaben für den aktuellen Permavar übernimmt.

Probieren Sie es 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 Bytes

SGthyXfa*

Dieselbe Idee wie bei der Antwort von @ flawr, bei der wir hijack strfind( Xf) verwenden, um die sortierte Version der Eingabe innerhalb der Verkettung von zwei Kopien der Eingabe zu finden.

Probieren Sie es online!

Erläuterung

        % 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 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Dies verkettet das Array x mit sich selbst und zählt die Anzahl der Paare, die nicht in Ordnung sind, dh die Anzahl der zusammenhängenden Unterarrays [a, b], für die b - a <0 ist . Wenn C die Anzahl der Paare von ungeordneten x selbst und t ist 1 , wenn x ‚s letzte Element größer ist als seine erste ist, sumkehrt 2c + t .

Das Array x ist driftsortierbar iff (c, t) = (1, 0) ( x muss auf den kleineren Wert des einzigen ungeordneten Paares gedreht werden), (c, t) = (0, 1) ( x ist sortiert) oder (c, t) = (0, 0) ( x ist sortiert und alle seine Elemente sind gleich), was wahr ist, wenn 2c + t <3 ist .

Javascript ES6, 48 45 43 Zeichen

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

Prüfung:

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 Bytes

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

Ich muss wirklich ein optionales Argument hinzufügen $( - circular permute left um mehr als einmal zu permutieren ... das wären 13 Bytes gewesen. Dies wird warten, nachdem ein stabiler neuer Transpiler in Prolog implementiert wurde.

Erläuterung

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 Bytes

Rekursive Funktion. Gibt zurück, nilwenn das Eingabearray nicht driftsortiert werden kann.

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

CJam, 17 13 Bytes

Vielen Dank an Dennis für das Speichern von 4 Bytes.

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

Ein unbenannter Block (Funktion), der eine Liste aufnimmt und zurückgibt.

Testsuite.

Erläuterung

Dies basiert im Wesentlichen auf der Beobachtung von xnor, dass die sortierte Liste doppelt so groß ist wie die ursprüngliche Liste, wenn ihre Drift sortierbar ist:

_$   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 Zeichen

#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;}}

Wenn ich die Ausgabe nicht leer lassen kann, 252 Zeichen 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<<'-';}

Ungolfed-Version 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: Basierend auf der Idee von @ MichelfrancisBustillos .

Java 7, 207 Bytes

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;}

Ausführlicher Versuch hier

// 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

druckt die Ausgabe als durch Leerzeichen getrennte Werte aus oder druckt ffür einen falschen Wert.

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);}

Durchläuft alle Kombinationen des Arrays von Ganzzahlen, bis die gültige Sequenz gefunden wird oder die Kombinationen ausgehen. Das Array wird nicht geändert, sondern die driftsortierte Sequenz wird als durch Leerzeichen getrennte Zeichenfolge gespeichert.

etwas besser lesbar:

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);
}

versuche es online

C 105 Bytes

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]);}

Dies akzeptiert die Eingabe-Ganzzahlen als separate Befehlszeilenargumente und gibt die Ausgabeliste als eine Ganzzahl pro Zeile aus.

Wenn die Liste nicht driftsortierbar ist, wird das Programm aufgrund einer Gleitkomma-Ausnahme vorzeitig beendet, sodass die leere Ausgabe eine leere Liste darstellt.

Nachprüfung

$ 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

Rubin, 28

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

Gibt entweder das sortierte Array oder nil(was ein falscher Wert ist) zurück, wenn die Eingabe nicht driftsortierbar ist.

Python, 53 Bytes

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

Wenn Sie dies testen möchten, gehen Sie zu https://www.repl.it/languages/python3 und fügen Sie Folgendes ein:

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

Wie es funktioniert:

• sist eine Variable, die die sortedPython-Funktion speichert, die Listen sortiert
• N ist die Hauptfunktion
• Die Eingabeliste sortiert: s(x)wird multipliziert mit, ob die Liste driftsortierbar ist oder nichtstr(s(x))[1:-1]in str(x+x) (dank @xnor)
  • Dies funktioniert, weil es [1,2,3,4]*falsezu einer leeren Liste kommt[]
  • und [1,2,3,4]*trueführt zu[1,2,3,4]

Python, 83 Bytes

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

Dies wurde durch die anderen Python-Antworten beschämt, aber ich könnte es genauso gut posten. Ich mag das wirklich nicht

range(len(l)))

Teil. Gibt es eine schnellere Möglichkeit, die Liste zu durchlaufen?

MATLAB / Octave, 118 Bytes

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 bis 80 Byte

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

Durchläuft die Eingabeliste $aund überprüft jedes paarweise Element (einschließlich des letzten und des ersten), um festzustellen, ob es mehr als ein abnehmendes Paar gibt. Wenn das bestimmte Paar abnimmt, dekrementieren wir $c. Gibt entweder die sortierte Liste oder ein einzelnes Element 0basierend auf dem Wert von aus$c am Ende aus. Wenn mehr als ein "schlechtes" Paar vorhanden ist, ist ++$ces immer noch negativ, andernfalls ist es zumindest 0so, dass das zweite Element des Pseudoternärs ausgewählt wird ( $a|sort).

Ich sehe, dass xnor etwas Ähnliches getan hat , aber ich habe es unabhängig erfunden .

Faktor 47 Bytes

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

Verbinden Sie die Sequenz mit sich selbst und prüfen Sie, ob die sortierte Wiedergabe des Originals eine Teilsequenz ist.

C ++, 313 359 370 Bytes

Ein großes Dankeschön an @Qwertiy, dass sie das zum Laufen gebracht und mir einige großartige Golfmethoden beigebracht haben!

Golf gespielt:

#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";}

Ungolfed:

#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

In Mathcad ist 0 (Skalar) == false.

Die (äquivalente) Byteanzahl ist TBD, bis eine Zählmethode vereinbart wurde. Ca. 52 Byte bei Verwendung einer Byte = Operator / Symbol-Tastaturäquivalenz.

Mathematica 55 50 61 58 Bytes

Mit 3 Bytes gespart dank Martin Büttner.

Meine früheren Versuche haben den gesamten Testfall nicht bestanden. Ich musste hinzufügen Union, um Wiederholungen in der Liste zu vermeiden, die der Reihe nach eingegeben wurden.

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

Tests

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}}

Erläuterung

Drehen Sie die Eingabeliste mit der rechten Maustaste von 1 zu nMal, wobei ndie Länge der Eingabeliste angegeben ist. Wenn die sortierte Eingabeliste zu den rotierten Ausgabelisten gehört, geben Sie sie zurück. Andernfalls geben Sie eine leere Liste zurück.

PHP, 98 Bytes

1Gibt ein if driftsortable aus, sonst nichts

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