Golf aleatorio del día # 1: baraja una matriz

35

Sobre la serie

Ejecutaré una pequeña serie de desafíos de código de golf que giran en torno al tema de la aleatoriedad. Básicamente será un campo de golf de 9 hoyos , pero se distribuirá en varias preguntas. Puede participar en cualquier desafío individualmente como si fuera una pregunta normal.

Sin embargo, mantendré una tabla de clasificación en todos los desafíos. La serie tendrá más de 9 desafíos (por ahora), uno publicado cada pocos días. Cada usuario que participa en los 9 desafíos es elegible para ganar la serie completa. Su puntaje general es la suma de sus presentaciones más cortas en cada desafío (por lo tanto, si responde un desafío dos veces, solo la mejor respuesta se cuenta para el puntaje). Si alguien ocupa el primer lugar en esta tabla de clasificación general durante 28 días , le otorgaré una recompensa de 500 repeticiones .

Aunque tengo un montón de ideas alineadas para la serie, los desafíos futuros aún no están establecidos en piedra. Si tiene alguna sugerencia, hágamelo saber en la publicación de sandbox relevante .

Hoyo 1: baraja una matriz

La primera tarea es bastante simple: dada una matriz no entera de enteros, baraja aleatoriamente. Sin embargo, hay algunas reglas:

  • Cada permutación posible debe devolverse con la misma probabilidad (por lo que la combinación aleatoria debe tener una distribución uniforme). Puede verificar si su algoritmo es uniforme / imparcial al implementarlo en JavaScript en Will it Shuffle , que producirá una matriz de los sesgos; el resultado debería verse tan uniforme como sus Fisher-Yates incorporados u ordenar (orden aleatorio) .
  • No debe utilizar ningún método incorporado o de terceros para barajar la matriz o generar una permutación aleatoria (o enumerar todas las permutaciones). En particular, la única función aleatoria incorporada que puede usar es obtener un solo número aleatorio a la vez . Usted puede asumir que cualquier incorporada de azar carreras método del número en O (1) y es perfectamente uniforme en el intervalo solicitado (en un sentido matemático - es posible ignorar los detalles de la representación de punto flotante aquí). Si su idioma le permite obtener una lista de m números aleatorios a la vez, puede usar esta función, siempre que los números m sean independientes entre sí y los cuente como O (m).
  • Su implementación no debe exceder una complejidad temporal de O (N) , donde N es el tamaño de la matriz que se barajará. Por ejemplo, no puede "ordenar por números aleatorios".
  • Puede barajar la matriz en su lugar o crear una nueva matriz (en cuyo caso, la matriz anterior puede modificarse como desee).

Puede escribir un programa completo o una función y recibir información a través de STDIN, argumento de línea de comando, argumento de función o solicitud y producir salida a través del valor de retorno o imprimiendo en STDOUT (o la alternativa más cercana). Si escribe una función que baraja la matriz en su lugar, no necesita devolverla, por supuesto (siempre que su idioma le permita acceder a la matriz modificada después de que la función regrese).

La entrada y la salida pueden estar en cualquier lista conveniente o formato de cadena, pero deben admitir enteros arbitrarios en el rango -2 31 ≤ x <2 31 . En principio, su código debería funcionar para matrices de hasta 2 31 de longitud , aunque esto no necesariamente tiene que caber en su memoria o completarse dentro de un período de tiempo razonable. (Simplemente no quiero ver límites de tamaño arbitrarios para los bucles de hardcode o algo así).

Este es el código de golf, por lo que gana el envío más corto (en bytes).

Tabla de clasificación

El siguiente fragmento generará una tabla de clasificación en todos los desafíos de la serie.

Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(El idioma no se muestra actualmente, pero el fragmento sí lo requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).

Martin Ender
fuente
77
Estoy decepcionado de que no se nos permita ser "inteligentes" y usar funciones de biblioteca que no sean "obtener un número aleatorio" . ¿Queremos ver otras 69 implementaciones de barajado de Fisher-Yates? Considere eliminar esta regla en futuras tareas. Además, ¿por qué un límite en la complejidad del tiempo? Considere relajarlo al menos a O (n ^ 2); También creo que alguien podría encontrar una implementación especialmente desarrollada si permite O (n!).
anatolyg
77
@anatolyg Eliminar las restricciones equivale a que cada respuesta sea sortby(random)(la razón de la restricción de tiempo) o simplemente .shuffle()(la razón de la restricción incorporada), que creo que es mucho menos inteligente que tener que implementar Fisher-Yates u otra enfoque.
Martin Ender
1
Si se baraja en su lugar, ¿una función tiene que devolver la matriz, o es suficiente que se modifique? ¿Puedo escribir una función para en shuffle(array)lugar de newArray=shuffle(array)?
Geobits
1
@Bakuriu Afirmar que puede ordenar en tiempo lineal si los números son fijos es un poco como afirmar que puede hacer cualquier cosa en O (1) si los tamaños de entrada son fijos. Además, la restricción relevante son las matrices de tamaño fijo, no los enteros de tamaño fijo, porque el tamaño de la matriz determina qué tan grande necesita que sean sus números aleatorios. De todos modos, la limitación en la complejidad del tiempo es, por supuesto, para el algoritmo general que implemente, mientras que los límites en los tamaños de entrada están en su lugar, por lo que no tiene que usar enteros de precisión arbitraria si su idioma no los usa de fábrica .
Martin Ender
2
¿Por qué la solución de Adám llega a 43319 bytes cuando en realidad es 14?
boboquack

Respuestas:

20

Dyalog APL, 25 24 bytes

Primero para la solución de 25 caracteres: i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕

                      a←⎕ ⍝ evaluated input, assign to "a"
                     ⍴a   ⍝ length
                    ⍳⍴a   ⍝ 1 2 .. length
                   ⌽⍳⍴a   ⍝ length .. 2 1
                 i←       ⍝ assign to "i"
                ?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
   a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
        ←                 ⍝ in Dyalog, assignment returns its right-hand side
  ⊃                       ⍝ first element, i.e. a[⍵]
                          ⍝ the result from {} is an array of all those a[⍵]

Después de algunas transformaciones de equivalencia en lo anterior:

i {}¨ ?i  ←→  i {}¨∘? i   ⍝ because A f∘g B ←→ A f g B
          ←→  {}¨∘?⍨ i    ⍝ because f⍨ B ←→ B f B

podemos deshacernos de la tarea i←y guardar un personaje:

{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕

ngn
fuente
3
... mente. estropeado.
danwyand
1
¿Un idioma que tengo que leer de derecha a izquierda? ¡Guauu!
Luminoso
55
@ Luminoso, como suele ser el caso con la notación matemática: sin cos ln sqrt x
ngn
44
@ngn cuando lo pones de esa manera eso hace que mi comentario anterior parezca ridículo. decir ah.
Luminoso
55
@ronalchn Hay 8 bits codificaciones para APL, como este uno o este otro; Yo Dyalog utiliza uno de estos, como una alternativa a Unicode.
anatolyg
12

80386 código máquina, 44 24 bytes

Hexdump del código:

60 8b fa 0f c7 f0 33 d2 f7 f1 49 8b 04 8f 87 04
97 89 04 8f 75 ed 61 c3

Gracias a FUZxxl, quien sugirió usar las rdrandinstrucciones.

Aquí está el código fuente (puede ser compilado por Visual Studio):

__declspec(naked) void __fastcall shuffle(unsigned size, int array[])
{
    // fastcall convention:
    // ecx = size
    // edx = array
    _asm
    {
        pushad;             // save registers
        mov edi, edx;       // edi now points to the array

    myloop:
        rdrand eax;         // get a random number
        xor edx, edx;
        div ecx;            // edx = random index in the array

        dec ecx;            // count down
        mov eax, [edi + 4 * ecx];   // swap elements
        xchg eax, [edi + 4 * edx];  // swap elements
        mov [edi + 4 * ecx], eax;   // swap elements
        jnz myloop;

        popad;              // restore registers
        ret;
    }
}

Otra implementación más de Fisher-Yates. La mayor parte del golf se logró pasando parámetros en registros.

anatolyg
fuente
1
También podría haber usado rdrandpara mierda y risas.
FUZxxl
@FUZxxl ¡Lo olvidé por completo! Lástima que elimina la parte más interesante de mi respuesta ...
anatolyg
9

Java, 88 101

Un barajado básico de Fisher-Yates hace el truco. Tengo la sensación de que se usará con bastante frecuencia aquí, ya que es rápido y fácil de implementar. Aquí hay algo de hacinamiento / asignación, pero honestamente no hay demasiado para jugar al golf; Es corto por naturaleza.

void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}

Con algunos saltos de línea:

void t(int[]s){
    for(int i=s.length,t,x;
        i>0;
        t=s[x*=Math.random()],
        s[x]=s[i],
        s[i]=t
    )
        x=i--;
}

Esto se baraja en su lugar, modificando la matriz original s[]. Programa de prueba:

public class Shuffle {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        new Shuffle().t(a);
        for(int b:a)
            System.out.print(b+" ");
    }
    void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}
}
Geobits
fuente
1
No, el desafío establece que puede asumir que " es perfectamente uniforme en el rango solicitado ". El rango solicitado de Math.random()tiene un tamaño que es una potencia de dos, por lo que esto no cumple con las especificaciones.
Peter Taylor
1
Las interpretaciones de @PeterTaylor Jan y Geobits son, de hecho, cómo pretendía la regla: que no tenga que preocuparse por la duración real del ciclo de su PRNG.
Martin Ender
1
@ MartinBüttner la duración del ciclo no es el problema aquí, eso está cubierto por su regla. La aspereza de los flotadores es.
John Dvorak
3
@TheBestOne Es un byte más corto que la única solución python publicada actualmente;)
Geobits
1
¡Ya no! : D
Sp3000
8

Python 2, 86 bytes

from random import*
def S(L):i=len(L);exec"i-=1;j=randint(0,i);L[i],L[j]=L[j],L[i];"*i

Esta es una función que baraja la matriz en su lugar sin devolverla, utilizando una implementación sencilla de la baraja Fisher-Yates . Obtener números aleatorios de Python es costoso ...

Gracias a @xnor y @colevk por los consejos.

Sp3000
fuente
Esa expresión de rango se ve bastante engorrosa. ¿Seguramente es más corto contar manualmente como while i:i-=1;...?
xnor
@xnor Sí, lo es, gracias por eso. Sigo olvidando que whiletiende a ser más corto que forpara este tipo de cosas ...
Sp3000
1
Awww ... ahora mi respuesta Java no está superando esto. Estuve bastante feliz por un tiempo muy corto :(
Geobits
Puede guardar otros 2 bytes haciendo i=len(L)y colocando la disminución al comienzo del ciclo while.
colevk
8

J, 45 44 caracteres

Esto fue complicado.

<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

Aquí hay una explicación:

  1. # y: El recuento de y, es decir, el número de elementos en y.
  2. ?@# y: Un número aleatorio distribuido uniformemente en el rango de 1a (#y)-1.
  3. x { y: El artículo desde el y índice x.
  4. (<<<x) { y: Todos los artículos excepto el artículo en el índice xen y.
  5. x , y: y anexado a x.
  6. x ({ , <^:3@[ { ]) y: El elemento en la posición xen y, a continuación, todos los demás elementos.
  7. (?@# ({ , <^:3@[ { ]) ]) yUn aleatorio de y, luego todos los demás elementos.
  8. x {. y: Los primeros xelementos tomados de y.
  9. x }. y: Los primeros xartículos se redujo desde y.
  10. x ({. , }.) y: Los primeros xelementos tomados de y, luego los primeros xelementos eliminados dey
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Los primeros xartículos tomadas desde y, entonces el primer xartículo de yprocesó como en el número 7.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: Lo mismo con la caída tirada para salvar a un personaje.
  13. u/ y: u insertado entre los elementos de y.
  14. < y: en y caja .
  15. <"0 y: Cada artículo de en y caja .
  16. i. y: enteros de 0a y - 1.
  17. i.@# y: enteros de 0a (#y) - 1.
  18. (<"0@i.@# , <) y: Números enteros de 0a (#y) - 1cada uno en cajas y luego yen una sola caja. Esto es necesario porque las matrices en J son uniformes. Una caja oculta la forma de su contenido.
  19. x u&v y: como (v x) u (v y).
  20. > y: y abierto , es decir, sin su caja.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y la frase del número 12 se aplica a sus argumentos sin caja.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ yla frase del número 21 insertada entre elementos de y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) yla frase del número 22 se aplica al resultado de la frase del número 18, o una permutación uniforme de los elementos de y.
FUZxxl
fuente
1
Simplemente no puedo distinguir todos los paréntesis. Y ese triple boxeo <@<@<@[también es un misterio ... Esperando explicación. :)
randomra
2
Una vez que esto se explique, podría ser mucho más probable que votara esta respuesta ;-)
John Dvorak
@randomra Aquí tienes.
FUZxxl
@ JanDvorak ¿Es satisfactoria la explicación?
FUZxxl
¡Gran explicación! No sabía sobre todo el uso en caja de from( {). Y realmente me gusta el &>/truco para manipular una lista. Estoy seguro de que podría haberlo usado un par de veces antes.
randomra
5

Pyth, 25 bytes

Pruébalo aquí.

Otra implementación más de Fisher-Yates. Es esencialmente lo mismo que la solución de Python @ Sp3000, solo en pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Gracias a @Jakube por el truco de intercambio

<implicit>    Q=input()
FNrlQ1        For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
 KON          K = random int 0-N
 J@QN         J=Q[N]
 <space>      Suppress print
 XXQN@QKKJ    Swap K and J
)             End for
Q             Print Q
Maltysen
fuente
Puede guardar dos bytes combinando esas dos asignaciones de lista: `XXQN @ QKKJ` en lugar de` XQN @ QK XQKJ`.
Jakube
@Jakube gracias por el consejo. Sabía que debía haber una forma de intercambiar valores en una lista, y esto es realmente inteligente. Debe agregarlo a la lista de consejos.
Maltysen
4

Perl, 68 56 44

Como muchas otras soluciones, esto utiliza el algoritmo de Fisher-Yates .

Usando el comentario de nutki , se guardan 12 caracteres usando en $_lugar de $iy realizando las operaciones en los índices de la matriz.

44:

sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}

56:

sub f{$i=@_;$j=int(rand$i),@_[$i,$j]=@_[$j,$i]while$i--}

Este es mi primer codegolf.

Bonsaigin
fuente
No es un mal comienzo, no sabía que se puede usar @_[...]como un valor así. Se puede jugar más al golf sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}.
nutki
3

C, 63 61 60 bytes

i,t;s(a,m)int*a;{for(;m;a[m]=t)t=a[i=rand()%m--],a[i]=a[m];}

Solo una implementación directa de Fischer-Yates que ordena la matriz dada en su lugar. Compila y enlaza perfectamente bien con el compilador visual studio (vs2013, no he probado las otras versiones) y el compilador Intel. La firma de la función de aspecto agradable es s(int array[], int length). Estoy legítimamente impresionado de vencer a Python y Ruby.

Esto asume que srand()se llama y rand () se implementa correctamente, pero creo que esta regla permite eso:

You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval

Versión bien formateada:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
seudónimo117
fuente
Creo que es suficiente hacer el encabezado de la función s(a,m)*a{, pero no estoy seguro y tampoco quiero probarlo. Es posible que desee hacer un xorintercambio, como en a[i]^=a[m]^=a[i]^=a[m]. Esto también evita la necesidad de declarar t.
FUZxxl
@FUZxxl Creo que un intercambio xor causa problemas si i==m.
Geobits
@Geobits de hecho. Perdí esa posibilidad.
FUZxxl
Solo estaba tratando de entender por qué eso no estaba funcionando ... debería haberlo recordado. También necesito s(a,m)int*apara Visual Studio y el compilador de Intel. No tengo gcc o clang instalados para probar, pero supongo que también se quejarán.
seudónimo117
Esto es bastante impresionante en el golf. Después de probar muchas modificaciones que no salvaron nada, logré ver una forma de guardar 2 caracteres. Si cambia el orden de intercambio para que se convierta en la primera declaración de intercambio t=a[i], puede mover la i=rand()%m--declaración dentro como el índice de matriz.
Runer112
3

Octava, 88 77 bytes

function s=r(s)for(i=length(s):-1:1)t=s(x=randi(i));s(x)=s(i);s(i)=t;end;end

Otra implementación de Fisher-Yates ... Debería ser bastante sencillo si agrego los retornos y el espaciado de línea habituales:

function s=r(s)
  for(i=length(s):-1:1) # Counting down from i to 1
    t=s(x=randi(i));    # randi is builtin number generator for an int from 0 to i
    s(x)=s(i);
    s(i)=t;
  end
end

Las palabras clave de "fin" realmente matan el puntaje de golf aquí, desafortunadamente. ¡Hola, puedo usar "end" en lugar de "endfor" y "endfunction"!

dcsohl
fuente
1
Para su información, los "bytes" no es realmente requeridos por el código, sólo hace que seguro que es un titular, que contiene una coma (para separar el idioma) y al menos un número después de la coma, y luego simplemente elige el último número que no está tachado. Sin embargo, tener "bytes" todavía es bueno. ;)
Martin Ender
1
Puede guardar 1 byte usando en numellugar de lenght. Como
beneficio
2

Java 8, 77

(x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};

Es una lambda que toma int[]y regresa vacía. Mi primer intento no pareció muy interesante, así que decidí que saliera lanzando una excepción.

Programa de prueba:

interface shuff {
    void shuff(int[] x);
}
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        shuff s = (x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};
        int[] x = {3, 9, 2, 93, 32, 39, 4, 5, 5, 5, 6, 0};
        try {
            s.shuff(x);
        } catch(ArrayIndexOutOfBoundsException _) {}
        for(int a:x) System.out.println(a);
    }
}
Feersum
fuente
1
¿No es una trampa usar un lambda para evitar tener que escribir una firma de función, cuando tienes que proporcionar un delegado para usar el lambda en cualquier lugar? Además ... ¿no puedes dejar los paréntesis Math.random()?
Rawling
1
@Rawling Podrías votar en esta meta pregunta . Actualmente, hay 9 votos a favor de lambdas y 0 en contra. Sí, los paréntesis se pueden eliminar.
feersum
Eh, si hay una meta publicación y un consenso hasta el momento, dispare. (Y disfruta el puntaje de golf de dos más bajo en mí: p)
Rawling
3
Creo que es injusto que la función se detenga por excepción en un caso normal, ¿verdad?
Qwertiy
1
@Qwertiy Para cada uno lo suyo ... Crees que es injusto, creo que es genial.
fiesta del
2

Golflua, 37

¿Cómo ejecutar Golflua?

~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$

La entrada se proporciona como una tabla en la variable X. La tabla se baraja en su lugar.

Ejemplo de uso:

> X={0,-45,8,11,2}
> ~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$
> w(T.u(X))
-45 0 8 11 2
mniip
fuente
2

R, 79 bytes

f=function(x){n=length(x);for(i in 1:n){j=sample(i:n,1);x[c(i,j)]=x[c(j,i)]};x}

Esta es una implementación sencilla del shuffle de Fisher-Yates. La función R sampleextrae una muestra aleatoria simple de un tamaño dado de un vector dado con igual probabilidad. Aquí estamos dibujando una muestra aleatoria de tamaño 1 en cada iteración de los enteros i, ..., n. Como se indicó en la pregunta, se puede suponer que esto es O (1), por lo que en toda esta implementación debe ser O (N).

Alex A.
fuente
2

Matlab, 67

También implementando Fisher-Yates.

a=input('');n=numel(a);for i=1:n;k=randi(i);a([i,k])=a([k,i]);end;a

Pensé que era una pena no poder usar la randpermfunción de Matlab . Pero después de jugar un poco, pensé que podría mirar la fuente de randpermpara ver cómo se hace, y me sorprendió ver que solo había una línea: [~,p] = sort(rand(1,n))=)

falla
fuente
2

Perl, 44

sub f{($_[$x],$_)=($_,$_[$x=rand++$i])for@_}

Otro perl en 44 caracteres. Ejemplo de uso:

@x=(1..9);f(@x);print@x
nutki
fuente
2

Mathematica, 82 90 83 93 bytes

Nota: Esta variación de la mezcla aleatoria de Fisher-Yates es en realidad la solución de Martin Büttner, con algunos códigos par alephalpha. ses la matriz de entrada. Nada sofisticado, pero a veces las cosas simples son las más esquivas.

f@s_:=(a=s;m=Length@a;Do[t=a[[r=RandomInteger@{1,m-1}]];a[[r]]=a[[m]]; a[[m]]=t,{n,1,m-1}];a)
DavidC
fuente
Puedes usar Doaquí. Es más corto que While.
alephalpha
2

Ruby, 57 bytes

->a{a.size.times{|i|j=rand(i+1);a[i],a[j]=a[j],a[i]};p a}

Entrada (como función lambda):

f.([1,2,3,4,5])

Salida:

[2, 1, 4, 3, 5]
Fibra cero
fuente
2

TI-BASIC, 46 bytes

For(X,dim(L1),2,-1:randInt(1,X→Y:L1(X→Z:L1(Y→L1(X:Z→L1(Y:L1

1   111   2  1111112       1111112 111112 1112 111112 1112

Fuente para el recuento de bytes

Ypnypn
fuente
1
Te estás perdiendo el End.
lirtosiast
2

K, 31 caracteres

f:{{l[i:x,1?x]:l@|i}'|!#l::x;l}

No es tan corta como la que he puesto antes (que fue descalificado) ... oh bien.

Es un barajado básico de Fisher-Yates. Esto fue construido con mucha ayuda de la lista de correo de Kona .

kirbyfan64sos
fuente
2

JavaScript (ES6), 66

Esta función baraja la matriz en su lugar. También devuelve una matriz de subproductos que NO es la salida barajada y no debe considerarse.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)
edc65
fuente
2

MATL , 16 bytes

XH`HnYr&)XHxvHHn

Pruébalo en línea!

Fisher-Yates en MATL. Casi un tercio de este programa está dedicado a la letra H, que corresponde a la función del portapapeles en MATL.

Básicamente, Halmacena los elementos no utilizados de la entrada, mientras que la pila realiza un seguimiento de la lista aleatoria.

Sanchises
fuente
2

Japt, 12

rÈiMqZÄ Y}[]

¡Intentalo!

-10 (aproximadamente la mitad;) gracias a @Shaggy!

Tenía muchas ganas de probar un lenguaje de golf, y el intérprete de Japt tenía una buena documentación y una forma de probar las cosas en el navegador.

A continuación se muestra la estrategia que tomé:

  • Reduce la siembra de entrada con una matriz vacía
  • En cada paso, encuentre una ranura aleatoria para insertar el elemento actual
dana
fuente
1
Bienvenido a Japt, es bueno tenerte con nosotros. Creo que esto funciona para 9 bytes, utilizando el mismo método. Sin embargo, si el RNG no es satisfactorio, intente esto en su lugar.
Shaggy
@ Shaggy - ¡Gracias por los consejos! :) Terminé usando una versión ligeramente modificada de su segunda solución. Como el tercer parámetro de la función reducir es un índice, ya conocemos la longitud.
dana
1

Javascript ES6, 69

a=>{m=a.length;while(m)[a[m],a[i]]=[a[i=~~(Math.random()*m--)],a[m]]}

Es Fisher-Yates.

PD: se puede probar en Firefox

Qwertiy
fuente
@ MartinBüttner, lo eliminó :)
Qwertiy
1

Pyth, 27 bytes

Pruébalo aquí

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

Esta es una implementación del shuffle incremental de Fisher-Yates, mencionado aquí en segundo lugar .

isaacg
fuente
1

Haskell, 170

import System.Random
import Data.Array.IO
s a=do(_,n)<-getBounds a;sequence$map(\i->do j<-randomRIO(i,n);p<-a%i;q<-a%j;writeArray a j p;return q)[1..n]where(%)=readArray

Otra solución de Fisher-Yates inspirada en el algoritmo en https://wiki.haskell.org/Random_shuffle .

s es una función que tiene firma: IOArray Int a -> IO [a]

Jmac
fuente
1

CJam - 30

q~_,,W%{_I=I)mr:J2$=@I@tJ@t}fI

Pruébalo en http://cjam.aditsu.net/

Entrada de ejemplo: [10 20 30 40 50]
Salida de ejemplo: 3020401050(agregue un pal final del código para una impresión bonita)

Si se permite que el código tome la entrada de la pila (como una función), entonces los primeros 2 caracteres se pueden eliminar, reduciendo el tamaño a 28.

Explicación:

El código es más largo de lo que esperaba, debido a la falta de un operador "swap" para las matrices
(que se implementará más adelante: p)

q~            read and evaluate the input (let's call the array "A")
_,,           make an array [0 1 2 ... N-1] where N is the size of A
W%            reverse the array, obtaining [N-1 ... 2 1 0]
{…}fI         for I in this array
    _I=       push A[I]
    I)mr:J    push a random number from 0 to I (inclusive) and store it in J
              stack: A, A[I], J
    2$=       get A[J]
    @I@t      set A[I] = A[J]
              stack: former A[I], A
    J@t       set A[J] = former A[I]
aditsu
fuente
Como se menciona en los comentarios, me temo que esto no es válido. Al menos _es O (N) (dentro de un bucle O (N)). Desafortunadamente, no veo una manera de evitar eso en CJam.
Martin Ender
Las listas se manejan como objetos inmutables, por lo que la duplicación solo se implementa como duplicar la referencia. En realidad, es lo tque lo mata, ya que no puede mutar la lista y ahora debe crear una copia.
Runer112
@ MartinBüttner Estaba a punto de publicar lo mismo que Runer112; Sí que puede haber un problema con el t, me gustaría mejorarlo en futuras versiones ..
aditsu
Por lo tanto, este código sigue el espíritu de la pregunta, pero no la "carta", debido a problemas de implementación del lenguaje interno.
aditsu
1

JavaScript (ES 6), 61

S=a=>(a.map((c,i)=>(a[i]=a[j=Math.random()*++i|0],a[j]=c)),a)

Puede probarlo aquí simplemente agregando una línea que diga shuffle = S(solo Firefox).

core1024
fuente
1

STATA, 161

di _r(s)
set ob wordcount($s)
token $s
g a=0
foreach x in $s{
gl j=floor(runiform()*_n)+1
replace a=`$j' if word($s,_n)=`x'
replace a=`x' if word($s,_n)=`$j'
}
l

Espera entrada como números separados por espacios. Si lo desea, puedo eliminar los encabezados y los números de observación de la salida, pero de lo contrario, esto es más corto.

comentarios
fuente
Que hay _nen esto
Martin Ender
_n es el número de la observación actual.
Comentarios
1

Java, 93 bytes

a->{for(int b=0,c,d=0,e=a.length;b<e;c=a[b],a[b]=a[d],a[d]=c,b++,d=b)d+=Math.random()*(e-b);}

Ejemplo de uso: http://ideone.com/RqSMnZ

El numero uno
fuente
1

SQF, 91 bytes

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i
Οurous
fuente
1
Esto está sesgado (ver "swap (i <-> random)" en Will It Shuffle), pero puedes convertirlo en Fisher-Yates (que es imparcial) reemplazándolo %xpor %i.
Martin Ender