Driftsort est un moyen simple de "trier" un tableau. Il fonctionne en «faisant glisser» ou en «tournant» les éléments dans le tableau jusqu'à ce que le tableau soit trié ou jusqu'à ce que le tableau ne soit pas trié.

Passons en revue deux exemples. Tout d'abord, considérez le tableau [10, 2, 3, 4, 7]. Comme le tableau n'est pas trié, nous le faisons pivoter une fois. (Cela peut se produire dans les deux sens, tant qu'il reste dans la même direction.) Ensuite, le tableau devient:

[7, 10, 2, 3, 4]

Ce n'est pas trié, alors nous tournons à nouveau.

[4, 7, 10, 2, 3]

Et encore:

[3, 4, 7, 10, 2]

Et une dernière fois:

[2, 3, 4, 7, 10]

Et c'est trié! Le tableau [10, 2, 3, 4, 7]est donc dérivable. Voici toutes les rotations du tableau, pour plus de clarté:

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

Considérez maintenant le tableau [5, 3, 9, 2, 6, 7]. Regardez ses rotations:

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

Aucun de ces tableaux n'est trié, donc le tableau [5, 3, 9, 2, 6, 7]n'est pas dérivable.

Objectif Étant donné un tableau / une liste d'entiers non vides comme entrée dans un programme / une fonction, implémentez la dérive sur l'entrée et la sortie, ou affichez une valeur de falsey ( ou un tableau / liste vide) si elle ne peut pas être dérivée. Les entiers sont liés à vos langues max / min, mais cela doit être au moins 255 pour le max et 0 pour le min.

Vous pouvez utiliser des méthodes de tri intégrées, mais pas une méthode intégrée qui résout le problème.

Il s'agit d'un code-golf , donc le programme le plus court en octets.

Cas de test

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]

Gelée , 6 octets

ṙỤċṢȧṢ

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça marche

ṙỤċṢȧṢ  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.

Rubis, 33

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

a.any?se déclenche jusqu'à une fois pour chaque élément du tableau, sauf qu'il s'arrête (et renvoie vrai) dès que le tableau a été muté dans un état trié. Si cela se produit, nous renvoyons le tableau muté. Sinon, nous retournons la fausse valeur qui any?revient.

Python 2, 51 octets

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

Ne prend pas la peine de tourner. Au lieu de cela, trie la liste, puis voit si l'original est triable par dérive en vérifiant s'il y a au plus une diminution parmi les éléments consécutifs de la liste cyclifiée. Le nombre est <3dû au fait que mapla liste la plus courte est remplie Noneà la fin, ce qui ajoute une fausse diminution.

Pyth, 9 octets

*SQ}SQ.:+

Explication:

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

Essayez-le ici!

Ou utilisez une suite de tests!

Matlab, 61 47 41 octets

Merci @Suever pour -6 octets!

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

Si strfind([a,a],sort(a))essaie de trouver le vecteur d'entrée trié en tant que «sous-chaîne» de l'élément non trié, il a été ajouté à lui-même. Si vrai, l'entrée est dérivable et nous obtenons un vecteur de longueur 2, sinon nous obtenons un vecteur vide. mintransforme simplement cela en un nombre / vecteur vide. L'ajout du vecteur trié à 0 l'affiche simplement, l'ajout à un vecteur vide génère une erreur.

Julia, 71 66 52 octets

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

Il s'agit d'une fonction anonyme qui accepte un tableau et renvoie un tableau ou un booléen. Pour l'appeler, affectez-le à une variable.

Pour un tableau d'entrée x , nous construisons l'ensemble de toutes les rotations de x et vérifions si la version triée x est un élément de cette liste. Si c'est le cas, nous renvoyons x trié, sinon nous retournons faux.

19 octets enregistrés grâce à Dennis!

Pip , 15 + 1 = 17 16 octets

Ugh, les autres langues de golf soufflent cela hors de l'eau. Cependant, puisque je l'ai déjà écrit ...

L#gI$<gPBPOgYgy

Prend les entrées sous forme d'arguments de ligne de commande séparés par des espaces. Nécessite -pou un autre indicateur de formatage de tableau pour afficher le résultat de manière lisible plutôt que concaténé. Le faux cas produit une chaîne vide, qui est visible grâce à la nouvelle ligne de fin.

                 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 octets

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

Retourne 0en cas d'échec. La version précédente de 85 83 80 octets évitait d'appeler 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)

Modifier: enregistré 2 octets en initialisant cà -1au lieu de 0. 5 octets enregistrés en passant de reduceà map, soupir ...

05AB1E , 12 octets

Code:

DgFÀÐ{Qi,}}0

Utilise l' encodage CP-1252 . Essayez-le en ligne! .

Snowman 1.0.2 , 27 octets

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

Il s'agit d'un sous-programme qui prend des entrées et des sorties vers le permavar actuel.

Essayez-le en ligne!

((                       ))  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 octets

SGthyXfa*

La même idée que la réponse de @ flawr où nous détournons strfind( Xf) pour trouver la version triée de l'entrée dans la concaténation de deux copies de l'entrée.

Essayez-le en ligne!

Explication

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

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

Essayez-le en ligne!

Comment ça marche

Cela concatène le tableau x avec lui-même et compte le nombre de paires qui sont en désordre, c'est-à-dire le nombre de sous-réseaux contigus [a, b] pour lesquels b - a <0 . Si c est le nombre de paires non ordonnées de x lui-même et t est 1 si le dernier élément de x est plus grand que son premier, sumrenverra 2c + t .

Le tableau x est dérivable ssi (c, t) = (1, 0) ( x doit être tourné à la plus petite valeur de la seule paire non ordonnée), (c, t) = (0, 1) ( x est trié) ou (c, t) = (0, 0) ( x est trié et tous ses éléments sont égaux), ce qui est vrai si 2c + t <3 .

Javascript ES6, 48 45 43 caractères

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

Tester:

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 octets

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

J'ai vraiment besoin d'ajouter un argument facultatif à $( - circular permute left pour permuter plus d'une fois ... cela aurait été de 13 octets. Cela attendra après avoir implémenté un nouveau transpilateur stable dans Prolog.

Explication

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

Rubis, 47 octets

Fonction récursive. Renvoie nilsi le tableau d'entrée ne peut pas être dérivé.

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

CJam, 17 ans 13 octets

Merci à Dennis d'avoir économisé 4 octets.

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

Un bloc sans nom (fonction) qui prend et renvoie une liste.

Suite de tests.

Explication

Cela utilise essentiellement l'observation de xnor que la liste triée apparaît deux fois dans la liste d'origine si sa dérive est triable:

_$   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 caractères

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

Si je ne peux pas laisser la sortie vide, 252 caractères 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<<'-';}

Version non golfée 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: Basé sur l' idée de @ MichelfrancisBustillos .

Java 7, 207 octets

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

Essai détaillé ici

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

imprime la sortie sous forme de valeurs séparées par des espaces ou imprime fpour une valeur de 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);}

parcourt toutes les combinaisons du tableau d'entiers jusqu'à ce qu'il trouve la séquence valide ou qu'il manque de combinaisons. le tableau n'est pas modifié, mais à la place la séquence dérivée est stockée sous forme de chaîne délimitée par des espaces.

un peu plus lisible:

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

essayez-le en ligne

C, 105 octets

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

Cela accepte les entiers d'entrée comme arguments de ligne de commande séparés et imprime la liste de sortie sous la forme d'un entier par ligne.

Si la liste n'est pas dérivable, le programme se ferme prématurément en raison d'une exception à virgule flottante, donc sa sortie vide représente une liste vide.

Vérification

$ 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

Rubis, 28

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

Renvoie le tableau trié ou nil(qui est une valeur fausse) si l'entrée n'est pas triable par dérive.

Python, 53 octets

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

Si vous voulez tester cette tête sur https://www.repl.it/languages/python3 et copiez-collez ceci:

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

Comment ça marche:

• s est une variable stockant le sorted fonction python qui trie les listes
• N est la fonction principale
• La liste d'entrée triée: s(x)est multipliée par la possibilité ou non de dériver la listestr(s(x))[1:-1]in str(x+x) (grâce à @xnor)
  • Cela fonctionne parce que [1,2,3,4]*false résultats dans une liste vide[]
  • et se [1,2,3,4]*truetraduit par[1,2,3,4]

Python, 83 octets

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

Cela a été honteux par les autres réponses en python, mais je pourrais aussi bien le poster de toute façon. Je n'aime vraiment pas

range(len(l)))

partie. Existe-t-il un moyen plus rapide de parcourir la liste?

MATLAB / Octave, 118 octets

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 octets

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

Parcourt la liste d'entrée $a, vérifiant chaque élément par paire (y compris le dernier et le premier) pour voir s'il y a plus d'une paire décroissante. Si la paire particulière diminue, nous décrémentons $c. Génère la liste triée ou un élément unique 0, en fonction de la valeur de $cà la fin. Si plus d'une "mauvaise" paire est présente, alors elle ++$csera toujours négative, sinon ce sera au moins 0, donc le deuxième élément du pseudo-ternaire est choisi ($a|sort ).

Je vois que xnor a fait quelque chose de similaire , mais je l'ai trouvé indépendamment.

Facteur, 47 octets

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

joindre la séquence sur elle-même, puis vérifier si le rendu trié de l'original est une sous-séquence.

C ++, 313 359 370 octets

Un grand merci à @Qwertiy pour avoir fait fonctionner cela et pour m'avoir enseigné d'excellentes méthodes de golf!

Golfé:

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

Non golfé:

#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, à déterminer

Dans Mathcad, 0 (scalaire) == false.

Le nombre d'octets (équivalent) est à déterminer jusqu'à ce que la méthode de comptage soit convenue. Environ 52 octets en utilisant un octet = équivalence clavier opérateur / symbole.

Mathematica 55 50 61 58 octets

Avec 3 octets enregistrés grâce à Martin Büttner.

Mes tentatives précédentes n'ont pas réussi tous les tests. Je devais ajouter Unionpour éviter les répétitions dans la liste qui étaient entrées dans l'ordre.

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

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

Explication

Faites pivoter vers la droite la liste d'entrée de 1 à nfois, où nest la longueur de la liste d'entrée. Si la liste d'entrée triée fait partie des listes tournées en sortie, renvoyez-la; sinon retournez une liste vide.

PHP, 98 octets

Produit un 1si dérivable, sinon rien

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