Driftsort es una forma simple de "ordenar" una matriz. Funciona "deslizando" o "girando" los elementos sobre la matriz hasta que se ordena la matriz, o hasta que la matriz no se puede ordenar.

Veamos dos ejemplos. Primero, considere la matriz [10, 2, 3, 4, 7]. Como la matriz no está ordenada, la rotamos una vez. (Esto puede suceder en cualquier dirección, siempre que siga siendo la misma dirección). Luego, la matriz se convierte en:

[7, 10, 2, 3, 4]

Esto no está ordenado, por lo que giramos nuevamente.

[4, 7, 10, 2, 3]

Y otra vez:

[3, 4, 7, 10, 2]

Y un tiempo final:

[2, 3, 4, 7, 10]

¡Y está ordenado! Entonces, la matriz [10, 2, 3, 4, 7]es derivable clasificable. Aquí están todas las rotaciones de la matriz, para mayor claridad:

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

Considere ahora la matriz [5, 3, 9, 2, 6, 7]. Mira sus rotaciones:

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

Ninguno de estos arreglos está ordenado, por lo que el arreglo [5, 3, 9, 2, 6, 7]no es derivable.

Objetivo Dada una matriz / lista de enteros no vacía como entrada a un programa / función, implementar driftsort en la entrada y salida, o generar un valor falsey ( o una matriz / lista vacía) si no se puede derivar. Los enteros están vinculados a sus idiomas max / min, pero esto debe ser al menos 255 para el máximo y 0 para el mínimo.

Puede utilizar métodos de clasificación integrados, pero no uno integrado que resuelva el desafío.

Este es un código de golf , por lo que el programa más corto en bytes.

Casos de prueba

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]

Jalea , 6 bytes

ṙỤċṢȧṢ

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

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

Rubí, 33

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

a.any?se dispara hasta una vez por cada elemento de la matriz, excepto que se detiene (y devuelve verdadero) tan pronto como la matriz ha mutado a un estado ordenado. Si esto sucede, devolvemos la matriz mutada. De lo contrario, devolvemos el valor falso que any?devuelve.

Python 2, 51 bytes

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

No se molesta en girar. En su lugar, ordena la lista, luego ve si el original se puede ordenar por deriva comprobando si hay como máximo una disminución entre los elementos consecutivos de la lista ciclada. El conteo se <3debe a que maprellena la lista más corta Noneal final, agregando una disminución falsa.

Pyth, 9 bytes

*SQ}SQ.:+

Explicación:

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

Pruébalo aquí!

¡O use una suite de prueba!

Matlab, 61 47 41 bytes

¡Gracias @Suever por -6 bytes!

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

Si strfind([a,a],sort(a))intenta encontrar el vector de entrada ordenado como una 'subcadena' del no ordenado, eso se agregó a sí mismo. Si es verdadero, la entrada es derivable y obtenemos un vector de longitud 2, si no, obtenemos un vector vacío. minsimplemente transforma esto en un número / vector vacío. Agregar el vector ordenado a 0 solo lo muestra, agregarlo a un vector vacío arroja un error.

Julia, 71 66 52 bytes

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

Esta es una función anónima que acepta una matriz y devuelve una matriz o un booleano. Para llamarlo, asígnelo a una variable.

Para una matriz de entrada x , construimos el conjunto de todas las rotaciones de x y verificamos si la versión ordenada x es un elemento de esa lista. Si es así, devolvemos x ordenado, de lo contrario devolvemos falso.

¡Ahorró 19 bytes gracias a Dennis!

Pipa , 15 + 1 = 17 16 bytes

Ugh, los otros idiomas de golf están sacando esto del agua. Sin embargo, como ya lo he escrito ...

L#gI$<gPBPOgYgy

Toma datos como argumentos de línea de comandos separados por espacios. Requiere -pu otro indicador de formato de matriz para mostrar el resultado de forma legible en lugar de concatenado. El caso falso genera una cadena vacía, que es visible en virtud de la nueva línea final.

                 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)

Retornos 0en caso de falla. La versión anterior 85 83 de 80 bytes evitó llamar 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)

Editar: se guardaron 2 bytes al inicializar cen -1lugar de 0. Guardado 5 bytes al cambiar de reducea map, suspiro ...

05AB1E , 12 bytes

Código:

DgFÀÐ{Qi,}}0

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Muñeco de nieve 1.0.2 , 27 bytes

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

Esta es una subrutina que toma entradas y salidas del permavar actual.

Pruébalo en línea!

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

La misma idea que la respuesta de @ flawr donde secuestramos strfind(Xf ) para encontrar la versión ordenada de la entrada dentro de la concatenación de dos copias de la entrada.

Pruébalo en línea!

Explicación

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

Pruébalo en línea!

Cómo funciona

Esto concatena el conjunto x consigo mismo y cuenta el número de pares que están fuera de orden, es decir, el número de subconjuntos contiguos [a, b] para los cuales b - a <0 . Si c es el número de pares desordenados de x y t es 1 si el último elemento de x es mayor que el primero, sumdevolverá 2c + t .

La matriz x se puede derivar si iff (c, t) = (1, 0) ( x tiene que rotarse al valor más pequeño del único par desordenado), (c, t) = (0, 1) ( x se ordena) o (c, t) = (0, 0) ( x se ordena y todos sus elementos son iguales), lo cual es cierto si f 2c + t <3 .

Javascript ES6, 48 45 43 caracteres

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

Prueba:

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.

Realmente necesito agregar un argumento opcional para $( - circular permute left para permutar más de una vez ... esto habría sido 13 bytes. Esto esperará después de implementar un nuevo transpilador estable en Prolog.

Explicación

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

Función recursiva. Devuelve nilsi la matriz de entrada no puede desviarse.

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

CJam, 17 13 bytes

Gracias a Dennis por guardar 4 bytes.

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

Un bloque (función) sin nombre que toma y devuelve una lista.

Banco de pruebas.

Explicación

Básicamente, esto utiliza la observación de xnor de que la lista ordenada aparece en el doble de la lista original si es derivable:

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

#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 no puedo dejar la salida vacía, 252 caracteres 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<<'-';}

Versión sin golf 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 << '-';
}

PD: Basado en la idea de @ 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;}

Prueba detallada aquí

// 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 salida como valores separados por espacios, o imprime fpara un valor 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);}

pasa por todas las combinaciones de la matriz de enteros hasta que encuentra la secuencia válida o se queda sin combinaciones. la matriz no se modifica, sino que la secuencia ordenada a la deriva se almacena como una cadena delimitada por espacios.

un poco más legible:

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

pruébalo en línea

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

Esto acepta los enteros de entrada como argumentos de línea de comandos separados e imprime la lista de salida como un entero por línea.

Si la lista no es derivable, el programa se cierra prematuramente debido a una excepción de coma flotante, por lo que su salida vacía representa una lista vacía.

Verificación

$ 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

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

Devuelve la matriz ordenada o nil(que es un valor falso) si la entrada no se puede ordenar por deriva.

Python, 53 bytes

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

Si desea probar esto, diríjase a https://www.repl.it/languages/python3 y copie y pegue esto:

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

Cómo funciona:

• s es una variable que almacena el sorted función python que clasifica las listas
• N es la función principal
• La lista de entrada ordenada: s(x)se multiplica por si la lista es o no derivablestr(s(x))[1:-1]in str(x+x) (gracias a @xnor)
  • Esto funciona porque [1,2,3,4]*false da resultado una lista vacía[]
  • y [1,2,3,4]*trueresultados en[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

Esto fue avergonzado por las otras respuestas de Python, pero también podría publicarlo de todos modos. Realmente no me gusta el

range(len(l)))

parte. ¿Hay alguna forma más rápida de recorrer la lista?

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 80 bytes

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

Recorre la lista de entrada $a, verificando cada elemento por pares (incluyendo el último y el primero) para ver si hay más de un par decreciente. Si el par particular está disminuyendo, disminuimos $c. Emite la lista ordenada o un elemento único 0, en función del valor de $cal final. Si está presente más de un par "malo", ++$cseguirá siendo negativo, de lo contrario será al menos 0, por lo que se elige el segundo elemento del pseudoternario ($a|sort ).

Veo que Xnor hizo algo similar , pero se me ocurrió esto de forma independiente.

Factor, 47 bytes

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

une la secuencia sobre sí misma, luego verifica si la versión ordenada del original es una subsecuencia.

C ++, 313 359 370 bytes

¡Un gran agradecimiento a @Qwertiy por hacer que esto funcione y por enseñarme algunos excelentes métodos de golf!

Golfizado:

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

Sin 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, TBD

En Mathcad, 0 (escalar) == falso.

El recuento de bytes (equivalente) es TBD hasta que se acuerde el método de recuento. Aproximadamente 52 bytes usando una equivalencia de teclado byte = operator / symbol.

Mathematica 55 50 61 58 bytes

Con 3 bytes guardados gracias a Martin Büttner.

Mis intentos anteriores no pasaron todo el caso de prueba. Necesitaba agregar Unionpara evitar repeticiones en la lista que fueron ingresadas en orden.

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

Pruebas

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

Explicación

Gire a la derecha la lista de entrada de 1 a nveces, donde nestá la longitud de la lista de entrada. Si la lista de entrada ordenada se encuentra entre las listas giradas de salida, devuélvala; de lo contrario, devuelve una lista vacía.

PHP, 98 bytes

Emite a 1si deriva derivable, de lo contrario nada

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