El objetivo de este rompecabezas es tomar un mazo de 52 cartas y barajarlo para que cada carta esté en una posición aleatoria.

Dado:

• Una matriz, deckde 52 enteros distintos que representan las cartas. Cuando comienzas, deckcontiene exactamente una de cada tarjeta en un orden desconocido.
• Una función, int rand(min, max)que devuelve un entero aleatorio entre ints mine maxinclusive. Puede suponer que esta función es verdaderamente aleatoria.
• Una función, void swap(x, y)que intercambia dos cartas en el mazo. Si llama swap(x, y), las tarjetas en las posiciones xy ycambiarán de lugar.

Cuando:

• El programa llama shuffle()(o shuffle(deck)o deck.shuffle()o como quiera que se ejecute su implementación),

Luego:

• deck debe contener exactamente una de cada tarjeta en orden perfectamente aleatorio.

La captura:

No puedes declarar ninguna variable. Llama swapy randtanto como quieras, pero no puedes declarar ninguna variable propia. Esto incluye forcontadores de bucle, incluso los implícitos como en a foreach.

Aclaraciones:

• Puede cambiar detalles menores para adaptarlos al idioma elegido. Por ejemplo, puede escribir swappara cambiar dos enteros por referencia. Los cambios deberían ser para que esto funcione con su idioma, no para facilitar el rompecabezas.
• deck puede ser una variable global o puede tomarlo como parámetro.
• Puede hacer lo que quiera con el contenido deck, pero no puede cambiar su longitud.
• Sus tarjetas pueden estar numeradas del 0 al 51, del 1 al 52 o de lo que desee.
• Puede escribir esto en cualquier idioma, pero no hacer trampa con la shufflefunción incorporada de su idioma .
• Sí, podrías escribir la misma línea 52 veces. Nadie quedará impresionado.
• El tiempo de ejecución no importa, pero la verdadera aleatoriedad sí.
• Esto no es realmente golf de código, pero siéntase libre de minimizar / ofuscar su código.

Editar: código repetitivo y visualizador

Si usó .NET o JavaScript, aquí hay algunos códigos de prueba que pueden resultarle útiles:

JavaScript:

• Visualizador JavaScript rápido y sucio, con fuente de CoffeeScript: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
• Versión ejecutable (solo pegue en su shuffle()función): http://jsfiddle.net/4zxjmy42/

C#:

• Visualizador ASP.NET con código C # detrás: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
• Stub con sólo las swapy randde servicios públicos métodos: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41

Este código clasifica y baraja el mazo varios miles de veces y realiza algunas pruebas básicas de cordura: para cada barajado, verifica que hay exactamente 52 cartas en el mazo sin repeticiones. Luego, el visualizador traza la frecuencia de cada carta que termina en cada lugar del mazo, mostrando un mapa de calor en escala de grises.

La salida del visualizador debe verse como nieve sin un patrón aparente. Obviamente, no puede probar la verdadera aleatoriedad, pero es una forma rápida y fácil de verificar. Recomiendo usarlo o algo así, porque ciertos errores en el algoritmo de barajado conducen a patrones muy reconocibles en la salida. Aquí hay un ejemplo del resultado de dos implementaciones, una con una falla común:

La versión defectuosa baraja parcialmente el mazo, por lo que podría verse bien si examinaras la matriz a mano. El visualizador hace que sea más fácil notar un patrón.

JavaScript

Creo que esta es la forma prevista de solución, utilizo la tarjeta en la posición 0 para realizar un seguimiento del progreso, solo barajando las tarjetas que ya se han utilizado como contador, ¡esto alcanza el estándar 52! permutaciones con una distribución equitativa perfecta. El procedimiento se complica porque XOR swap no permite que un elemento se intercambie por sí mismo.

Editar: construí una clasificación que clasifica cada elemento en su lugar justo antes de usarlo, lo que permite que esto funcione con una matriz sin clasificar. También abandoné las llamadas recursivas a favor de un ciclo while.

deck=[]
for(a=0;a<52;a++){
    deck[a]=a
}
function swap(a,b){
    deck[a]=deck[b]^deck[a]
    deck[b]=deck[b]^deck[a]
    deck[a]=deck[b]^deck[a]
}
function rand(a,b){
    return Math.floor(Math.random()*(1+b-a))+a
}
function shuffle(){
    while(deck[0]!=0){ //Sort 0 into element 0
        swap(0,deck[0])
    }
    while(deck[0]<51){ //Run 51 times
        while(deck[deck[0]+1]!=deck[0]+1){ //Sort element deck[0]+1 into position deck[0]+1
            swap(deck[deck[0]+1],deck[0]+1)
        }
        swap(0,deck[0]+1) //Swap element deck[0]+1 into position 0, thus increasing the value of deck[0] by 1
        if(rand(0,deck[0]-1)){ //Swap the element at position deck[0] to a random position in the range 1 to deck[0]
            swap(deck[0],rand(1,deck[0]-1))
        }
    }
    if(rand(0,51)){ //Swap the element at position 0 to a random position
        swap(0,rand(1,51))
    }
}
for(c=0;c<100;c++){
    shuffle()
    document.write(deck+"<br>")
}

Haskell

Aquí hay una implementación sin puntos. Sin variables, parámetros formales o recursividad explícita. Yo solía lambdabot 's @plfunción refactorización ( 'sin sentido') un poco.

import Data.List
import Control.Applicative
import Control.Monad
import System.Random

shuffle :: [a] -> IO [a]
shuffle = liftM2 (<$>) ((fst .) . foldl' (uncurry ((. flip splitAt) . (.) .
          (`ap` snd) . (. fst) . flip flip tail . (ap .) . flip flip head .
          ((.) .) . (. (++)) . flip . (((.) . (,)) .) . flip (:))) . (,) [])
          (sequence . map (randomRIO . (,) 0 . subtract 1) . reverse .
          enumFromTo 1 . length)

main = print =<< shuffle [1..52]

Aquí está mi procedimiento de prueba para asegurarme de que los números se distribuyan uniformemente:

main = print . foldl' (zipWith (+)) (replicate 52 0)
       =<< replicateM 1000 (shuffle [1..52])

Aquí está el algoritmo original:

shuffle :: [a] -> IO [a]
shuffle xs = shuffleWith xs <$>
             sequence [randomRIO (0, i - 1) | i <- reverse [1..length xs]]

shuffleWith :: [a] -> [Int] -> [a]
shuffleWith xs ns = fst $ foldl' f ([], xs) ns where
    f (a,b) n = (x:a, xs++ys) where
        (xs, x:ys) = splitAt n b

J

Ignorando que el mazo es una variable, está lo obvio ...

52 ? 52

Por supuesto, si realmente quieres una función, existe esta, que funcionará incluso si olvidas eliminar los comodines (o intentas barajar algo que no sean cartas).

{~ (# ? #)

Así que eso...

shuffle =: {~ (# ? #)
deck =: i. 52
shuffle deck

Esto probablemente esté fuera de la intención de la pregunta, que sería implementar el shuffle usted mismo de rand ( ?). Podría hacerlo más tarde cuando no se supone que esté trabajando.

Explicación

Explicación de 52 ? 52:

• x ? y es x elementos únicos aleatorios de y.

La explicación de {~ (# ? #)es más difícil debido a los tenedores y ganchos . Básicamente, es lo mismo que shuffle =: 3 : '((# y) ? (# y)) { y', que tiene un argumento implícito ( y).

• # y da la longitud de y
• Esto le da 52? 52 como antes, que es una permutación aleatoria de 0..51
• x { y es el elemento de y en el índice x, o (en este caso) elementos en los índices en x.
• Esto le permite mezclar lo que se pasa, no solo los enteros.

Consulte el vocabulario J para obtener detalles de los operadores, aunque la sintaxis y la semántica son bastante complicadas debido a la programación tácita y de rango.

Pitón

import random
def rand(x, y):
 return random.randrange(x, y+1)

def swap(deck, x, y):
 deck[x] ^= deck[y]
 deck[y] ^= deck[x]
 deck[x] ^= deck[y]

def shuffle(deck):
 if len(deck)>1:
  deck[1:]=shuffle(deck[1:])
  if rand(0,len(deck)-1)>0:swap(deck, 0, rand(1, len(deck)-1))
 return deck

print shuffle(range(52))

Usando representación factoradic

En la representación factoradic de una permutación, un elemento i toma valores de 0 a Ni. Entonces, una permutación aleatoria es solo rand(0,i)para cada Ni.

En J:

? |.>:i.52
2 39 20 26 ... 2 0 1 0 0 0

donde ? xesta rand(0,x-1)y |.>:i.52esta52 51 ... 1

Entonces, si aes el valor de ITH factoradic, hacemos el canje: swap(deck[i], deck[i+a]). La lista de pares para intercambiar son:

(,. i.52) ,. (,. ((?|.>:i.52)+i.52))
0 33
1 20
2  3
...
49 50
50 50
51 51

El intercambio que usaremos funciona de esta manera:

deck
24 51 14 18 ...
deck =: 0 1 swap deck
51 24 14 18 ...

No es realmente "por referencia", pero no hay funciones reales en J.

Usaremos la longitud del mazo ( #deck) para evitar usar una constante.

Programa completo en J:

deck =: 52 ? 52                           NB. Initial random deck
swap =: 4 : 'deck =: (x { y) (|.x) } y'   NB. Given swap "function"
f =: 3 : 0                                NB. function that calls the swap for a pair
({.y) swap deck
}.y
)
f^:(#deck) (,.,.[:,.]+[:?[:|.>:) i.#deck

C#

Aquí está mi propia respuesta basada en el algoritmo de Fisher-Yates . Debería darle una combinación perfecta si su generador de números aleatorios es lo suficientemente bueno.

Versión inglesa:

1. Cambie repetidamente la tarjeta por deck[0]la que está en deck[v], donde ves el valor nominal de la tarjeta en deck[0]. Repetir hasta v == 0. Esto ordenará parcialmente el mazo, pero eso no importa. Ahora sabe que la Tarjeta 0 está en la parte delantera del mazo, lo que significa que puede robar ese espacio en la matriz y usarlo como contador de bucles. Este es el "truco" clave para el problema de las variables locales.
2. Comenzando en la posición 1 (la segunda carta en el mazo), intercambia la carta icon la que está en rand(i, 51). Tenga en cuenta que usted necesita rand(i, 51), NO rand(1, 51) . Eso no asegurará que cada carta sea aleatoria.
3. Conjunto deck[0]de nuevo a 0. Ahora toda la cartas se barajan a excepción de la primera tarjeta, de modo de intercambio deck[0]con deck[rand(0, 51)]y ya está.

Versión C #:

public static void shuffle(int[] deck)
{
    while (deck[0] > 0)
        swap(ref deck[0], ref deck[deck[0]]);

    for (deck[0] = 1; deck[0] < 52; deck[0]++)
        swap(ref deck[deck[0]], ref deck[rand(deck[0], 51)]);

    deck[0] = 0;
    swap(ref deck[0], ref deck[rand(0, 51)]);
}

Versión Javascript:

while (deck[0] > 0)
    swap(0, deck[0]);

for (deck[0] = 1; deck[0] < 52; deck[0]++)
    swap(deck[0], rand(deck[0], 52));

deck[0] = 0;
swap(0, rand(0, 52));

... donde swap(a, b)intercambia deck[a]con deck[b].

Rubí, una línea

¿Se considera esto hacer trampa? Debería ser lo más aleatorio posible.

deck=(0..51).to_a # fill the deck
deck[0..51] = (0..51).map{deck.delete_at(rand deck.length)}

(El randmétodo de Ruby solo toma un argumento y luego genera un número n tal que 0 <= número <argumento).

Además, similar a la solución Perl de sogart, pero que yo sepa, no sufre el problema:

deck = deck.sort_by{rand}

Ruby sort_by es diferente de sort: primero genera la lista de valores para ordenar la matriz, y solo luego la ordena por ellos. Es más rápido cuando es costoso descubrir la propiedad por la que estamos clasificando, algo más lento en todos los demás casos. También es útil en el código de golf: P

JavaScript

NOTA: Esta solución no es técnicamente correcta porque utiliza un segundo parámetro i, en la llamada a shuffle, que cuenta como una variable externa.

function shuffle(deck, i) {
    if (i <= 0)
        return;
    else {
        swap(deck[rand(0,i-1)], deck[i-1]);
        shuffle(deck, i - 1);
    }
}

Llamar con shuffle(deck,52)

Un ejemplo de trabajo completo (tuvo que modificarse swapligeramente porque no hay referencias de ints en JavaScript):

function rand(min, max) { return Math.floor(Math.random()*(max-min+1)+min); }
function swap(deck, i, j) {
    var t=deck[i];
    deck[i] = deck[j];
    deck[j] = t;
}

function shuffle(deck, i) {
    if (i <= 0)
        return;
    else {
        swap(deck, rand(0,i-1), i-1);
        shuffle(deck, i - 1);
    }
}

// create deck
var deck=[];
for(i=0;i<52;i++)deck[i]=i;
document.writeln(deck);
shuffle(deck,52);
document.writeln(deck);

C ++

#include <cstdlib>
#include <ctime>
#include <iostream>

int deck[52];

void swap(int a, int b) {
    deck[a] ^= deck[b];
    deck[b] ^= deck[a];
    deck[a] ^= deck[b];
}

int r(int a, int b) {
    return a + (rand() % (b - a + 1));
}

void s(int *deck) {
    swap(1, r(2, 51));
    deck[0] *= 100;

    for(deck[0] += 2; (deck[0] % 100) < 51; deck[0]++) {
        swap(deck[0] % 100,
          r(0, 1) ? r(1, (deck[0] % 100) - 1) : r((deck[0] % 100) + 1, 51));
    }
    swap(51, r(1, 50)); 

    deck[0] = (deck[0] - 51) / 100;
    swap(r(1, 51), 0);
}

int main(int a, char** c)
{
    srand(time(0));

    for (int i = 0; i < 52; i++)
        deck[i] = i;

    s(deck);
    s(deck);

    for (int i = 0; i < 52; i++)
        std::cout << deck[i] << " ";
}

Evita intercambiar elementos consigo mismos, por lo que debe llamar dos veces para ser aleatorio.

re

shuffle(int[] d){
    while(d.length){
        if([rand(0,d.length-1)!=0)swap(d[0],d[rand(1,d.length-1)]);
        d=d[1..$];
    }
}

Otra solución de Perl, que en realidad produce una salida distribuida uniformemente:

sub shuffle_integers {
    map int, sort {$a-int $a <=> $b-int $b} map $_+rand, @_;
}

say join " ", shuffle_integers 1 .. 52;

Esta solución utiliza Perl rand, que devuelve un número aleatorio x en el rango 0 ≤ x <1. Agrega un número aleatorio a cada número entero en la entrada, ordena los números de acuerdo con sus partes fraccionarias y finalmente elimina esas partes fraccionarias nuevamente. .

(Creo que el uso de las variables especiales $_, $ay $bcae dentro del espíritu del desafío, ya que así es como perl pasa la entrada mapy sort, y no se usan para ningún otro propósito en el código. En cualquier caso, creo en realidad son alias de los valores de entrada, no copias independientes Esto no es en realidad una reproducción aleatoria en el lugar, sin embargo;. tanto mapy sortcrean copias de la entrada en la pila).

Java

Me sorprende que nadie haya dicho lo obvio: (supondré que swap (x, x) no hace nada.

    static void shuffle(){
        swap(1,rand(0,1));
        swap(2,rand(0,2));
        swap(3,rand(0,3));
        swap(4,rand(0,4));
        swap(5,rand(0,5));
        swap(6,rand(0,6));
        swap(7,rand(0,7));
        swap(8,rand(0,8));
        swap(9,rand(0,9));
        swap(10,rand(0,10));
        swap(11,rand(0,11));
        swap(12,rand(0,12));
        swap(13,rand(0,13));
        swap(14,rand(0,14));
        swap(15,rand(0,15));
        swap(16,rand(0,16));
        swap(17,rand(0,17));
        swap(18,rand(0,18));
        swap(19,rand(0,19));
        swap(20,rand(0,20));
        swap(21,rand(0,21));
        swap(22,rand(0,22));
        swap(23,rand(0,23));
        swap(24,rand(0,24));
        swap(25,rand(0,25));
        swap(26,rand(0,26));
        swap(27,rand(0,27));
        swap(28,rand(0,28));
        swap(29,rand(0,29));
        swap(30,rand(0,30));
        swap(31,rand(0,31));
        swap(32,rand(0,32));
        swap(33,rand(0,33));
        swap(34,rand(0,34));
        swap(35,rand(0,35));
        swap(36,rand(0,36));
        swap(37,rand(0,37));
        swap(38,rand(0,38));
        swap(39,rand(0,39));
        swap(40,rand(0,40));
        swap(41,rand(0,41));
        swap(42,rand(0,42));
        swap(43,rand(0,43));
        swap(44,rand(0,44));
        swap(45,rand(0,45));
        swap(46,rand(0,46));
        swap(47,rand(0,47));
        swap(48,rand(0,48));
        swap(49,rand(0,49));
        swap(50,rand(0,50));
        swap(51,rand(0,51));
    }

OK, ok, puede ser más corto:

package stackexchange;

import java.util.Arrays;

public class ShuffleDry1
{
    static int[] deck = new int[52];

    static void swap(int i, int j){
        if( deck[i]!=deck[j] ){
            deck[i] ^= deck[j];
            deck[j] ^= deck[i];
            deck[i] ^= deck[j];
        }
    }

    static int rand(int min, int max){
        return (int)Math.floor(Math.random()*(max-min+1))+min;
    }

    static void initialize(){
        for( int i=0 ; i<deck.length ; i++ ){
            deck[i] = i;
            swap(i,rand(0,i));
        }
    }

    static void shuffle(){
        while( deck[0]!=0 ) swap(0,deck[0]);
        for( deck[0]=52; deck[0]-->1 ; ) swap(deck[0],rand(deck[0],51));
        swap(0,rand(0,51));
    }

    public static void main(String[] args) {
        initialize();
        System.out.println("init: " + Arrays.toString(deck));
        shuffle();
        System.out.println("rand: " + Arrays.toString(deck));
    }

}

Burlesco

¿Lo que realmente está pidiendo es una permutación aleatoria de una lista de enteros? r@nos dará todas las permutaciones, y solo seleccionaremos una aleatoria.

blsq ) {1 2 3}r@sp
1 2 3
2 1 3
3 2 1
2 3 1
3 1 2
1 3 2
blsq ) {1 2 3}r@3!!BS
2 3 1

Como necesitamos una aleatoriedad verdadera, algo que Burlesque no es capaz de hacer porque Burlesque no tiene funcionalidad de E / S, necesitaría proporcionar alguna fuente de aleatoriedad a través de STDIN.

Eso es probablemente algo que arreglaré en una versión posterior (es decir, generar una semilla aleatoria al inicio y empujarla a la pila secundaria o algo así, pero el Intérprete Burlesque en sí no tiene E / S).

Javascript

No estoy seguro de si es "trampa", pero mi solución utiliza la matriz local nativa de los argumentos de una función. Incluí mis propias funciones de rand() swap()y filldeck(). De nota interesante, esto debería funcionar con un mazo de cualquier tamaño.

    var deck = [];

    function shuffle(){
        main(deck.length);
    }

    function main(){
        arguments[0] && swap( arguments[0]-=1, rand(0, deck.length-1) ), main(arguments[0]);
    }

        function rand(min, max){
            return Math.floor( Math.random()*(max-min+1) )+min;
        }

        function swap(x, y){
            var _x = deck[x], _y = deck[y];
            deck[x] = _y, deck[y] = _x;
        }


        function filldeck(dL){
            for(var i=0; i<dL; i++){
                var ran = rand(1,dL);
                while( deck.indexOf(ran) >= 0 ){
                    ran = rand(1,dL);
                }
                deck[i] = ran;
            }
        }

    filldeck(52);
    shuffle();

Tcl , 32 bytes

timeFunción de abuso que sirve para medir cuánto tiempo se está ejecutando un script, pero también puede servir como un mecanismo de bucle sin declarar ninguna variable.

time {lswap $D [rand] [rand]} 52

Pruébalo en línea!

Perl: ¡esta no es una combinación adecuada como se explica en los comentarios!

my @deck = (0..51);
@deck = sort {rand() <=> rand()} @deck;
print join("\n",@deck);

Creo que no usé nada como un intercambio, etc. ¿Era eso necesario como parte del problema?

JavaScript 4 líneas

function shuffle() {
  while(deck[0]!=0)swap(deck[0],rand(1,51))
  while(deck[0]++!=104)swap(deck[0]%51+1,rand(1,51))
  deck[0]=0
  swap(0,rand(0,51))
}

Respuesta original que no fue lo suficientemente aleatoria. No se garantizó que el intercambio tocaría cada elemento de la baraja.

// shuffle without locals
function shuffle() {
  deck.map(function(){swap(deck[rand(0,51)],deck[rand(0,51)])});
}