Das Ziel dieses Puzzles ist es, ein Kartenspiel mit 52 Karten zu nehmen und es so zu mischen, dass sich jede Karte in einer zufälligen Position befindet.

Gegeben:

• Ein Array deckvon 52 verschiedenen Ganzzahlen, die die Karten darstellen. deckEnthält zu Beginn genau eine Karte in einer unbekannten Reihenfolge.
• Eine Funktion, int rand(min, max)die eine zufällige Ganzzahl zwischen ints minund maxinclusive zurückgibt . Sie können davon ausgehen, dass diese Funktion wirklich zufällig ist.
• Eine Funktion, void swap(x, y)die zwei Karten im Stapel vertauscht. Wenn Sie callen swap(x, y), wechseln die Karten an Positionen xund yStellen.

Wann:

• Das Programm ruft auf shuffle()(oder shuffle(deck)oder deck.shuffle()oder wie auch immer Ihre Implementierung es mag),

Dann:

• deck sollte genau eine von jeder Karte in vollkommen zufälliger Reihenfolge enthalten.

Der Fang:

Sie können keine Variablen deklarieren. Rufen Sie swapund randso oft Sie möchten auf, aber Sie können keine eigenen Variablen deklarieren. Dies schließt forSchleifenzähler ein - auch implizite wie in a foreach.

Klarstellungen:

• Sie können kleinere Details an Ihre gewählte Sprache anpassen. Beispielsweise können Sie schreiben swap, um zwei Ganzzahlen durch Verweis zu wechseln. Änderungen sollten darin bestehen, diese Arbeit mit Ihrer Sprache zu machen, nicht um das Rätsel zu vereinfachen.
• deck kann eine globale Variable sein oder als Parameter verwendet werden.
• Sie können alles tun, was Sie wollen, um den Inhalt von deck , aber Sie können die Länge nicht ändern.
• Ihre Karten können mit 0-51, 1-52 oder einer beliebigen Nummer versehen werden.
• Sie können dies in jeder Sprache schreiben, aber mit der in Ihrer Sprache integrierten shuffleFunktion können Sie nicht schummeln .
• Ja, Sie könnten die gleiche Zeile 52 Mal schreiben. Niemand wird beeindruckt sein.
• Die Ausführungszeit spielt keine Rolle, aber die wahre Zufälligkeit.
• Dies ist nicht wirklich Code-Golf, aber Sie können Ihren Code gerne minimieren / verschleiern.

Bearbeiten: Kesselschild-Code und Visualizer

Wenn Sie .NET oder JavaScript verwendet haben, finden Sie hier einige nützliche Testcodes:

JavaScript:

• Schneller JavaScript-Visualizer mit CoffeeScript-Quelle: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
• Lauffähige Version (fügen Sie einfach Ihre shuffle()Funktion ein): http://jsfiddle.net/4zxjmy42/

C #:

• ASP.NET Visualizer mit C # -CodeBehind: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
• Stub nur mit den Dienstprogrammmethoden swapund rand: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41

Dieser Code sortiert und mischt das Deck mehrere tausend Mal und führt einige grundlegende Vernunftstests durch: Bei jedem Mischen wird überprüft, ob sich genau 52 Karten ohne Wiederholungen im Deck befinden. Anschließend zeichnet der Visualizer die Häufigkeit jeder Karte auf, die an jeder Stelle im Stapel landet, und zeigt eine Graustufen-Heatmap an.

Die Ausgabe des Visualizers sollte wie Schnee ohne erkennbares Muster aussehen. Offensichtlich kann es keine echte Zufälligkeit beweisen, aber es ist eine schnelle und einfache Möglichkeit zur Stichprobenprüfung. Ich empfehle es oder ähnliches zu verwenden, da bestimmte Fehler im Mischalgorithmus zu sehr erkennbaren Mustern in der Ausgabe führen. Hier ist ein Beispiel für die Ausgabe von zwei Implementierungen, von denen eine einen gemeinsamen Fehler aufweist:

Die fehlerhafte Version mischt das Deck teilweise, sodass es gut aussehen kann, wenn Sie das Array von Hand untersuchen. Der Visualizer erleichtert das Erkennen eines Musters.

JavaScript

Ich glaube, dies ist die beabsichtigte Form der Lösung. Ich benutze die Karte in Position 0, um den Fortschritt zu verfolgen. Ich mische nur die Karten, die bereits als Zähler verwendet wurden. Dies erreicht den Standard 52! Permutationen mit perfekter Gleichverteilung. Die Prozedur wird durch den XOR-Austausch kompliziert, der nicht zulässt, dass ein Element von selbst ausgetauscht wird.

Bearbeiten: Ich habe eine Sortierung eingebaut, die jedes Element an der richtigen Stelle sortiert, bevor es verwendet wird, sodass dies mit einem unsortierten Array funktioniert. Ich habe auch rekursive Aufrufe zugunsten einer while-Schleife verworfen.

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

Hier ist eine sinnlose Umsetzung. Keine Variablen, formalen Parameter oder explizite Rekursion. Ich gebrauchte lambdabot ‚s @pl(‚sinnlos‘) Refactoring - Funktion eine ganze Menge .

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]

Hier ist meine Testprozedur, um sicherzustellen, dass die Nummern gleichmäßig verteilt sind:

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

Hier ist der ursprüngliche Algorithmus:

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

Das Ignorieren dieses Decks ist eine Variable, es gibt die offensichtliche ...

52 ? 52

Natürlich, wenn Sie wirklich eine Funktion wollen, gibt es diese, die auch dann funktioniert, wenn Sie vergessen, die Joker zu entfernen (oder versuchen, etwas anderes als Karten zu mischen).

{~ (# ? #)

Damit...

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

Dies liegt wahrscheinlich außerhalb der Absicht der Frage, die darin bestehen würde, die Zufallswiedergabe selbst von rand ( ?) aus zu implementieren . Ich könnte das später machen, wenn ich nicht arbeiten soll.

Erläuterung

Erklärung von 52 ? 52:

• x ? y ist x zufällige Unikate von y.

Erklärung von {~ (# ? #)ist wegen der Gabeln und der Haken härter . Grundsätzlich ist es dasselbe wie shuffle =: 3 : '((# y) ? (# y)) { y', das ein implizites Argument hat ( y).

• # y gibt die Länge von y an
• Das ergibt 52? 52 wie zuvor, das ist eine zufällige Permutation von 0..51
• x { y ist das Element von y im Index x oder (in diesem Fall) Elemente in den Indizes in x.
• Auf diese Weise können Sie alles mischen, was übergeben wird, nicht nur ganze Zahlen.

Siehe J Vocabulary für Details zu Operatoren, obwohl die Syntax und die Semantik aufgrund der Rang- und impliziten Programmierung ziemlich schwierig sind.

Python

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

Factoradic Representation verwenden

In der faktoradischen Darstellung einer Permutation nimmt ein Element i Werte von 0 bis Ni an. Eine zufällige Permutation gilt also nur rand(0,i)für jedes Ni.

In J:

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

wo ? xist rand(0,x-1)und |.>:i.52ist52 51 ... 1

Dann wenn a der Wert des i - ten factoradic ist, haben wir die Swap: swap(deck[i], deck[i+a]). Die Liste der auszutauschenden Paare lautet:

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

Der Swap, den wir verwenden werden, funktioniert folgendermaßen:

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

Es ist nicht wirklich "per Referenz", aber es gibt keine wirklichen Funktionen in J.

Wir werden Decklänge verwenden (#deck ), um die Verwendung einer Konstante zu vermeiden.

Gesamtprogramm in 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 #

Hier ist meine eigene Antwort basierend auf dem Fisher-Yates-Algorithmus . Sollte Ihnen ein perfektes Shuffle ermöglichen, wenn Ihr Zufallsgenerator gut genug ist.

Englische Version:

1. Tauschen Sie die Karte bei wiederholt deck[0]gegen die bei aus deck[v], wobei vder Nennwert der Karte bei ist deck[0]. Wiederhole bisv == 0 . Dadurch wird das Deck teilweise sortiert, aber das spielt keine Rolle. Sie wissen jetzt, dass sich Karte 0 vorne im Stapel befindet. Das heißt, Sie können diesen Bereich im Array stehlen und ihn als Schleifenzähler verwenden. Dies ist der Schlüssel "Betrug" für das Problem der lokalen Variablen.
2. Beginnen Sie bei Position 1 (der zweiten Karte im Stapel) und tauschen Sie die Karte um igegen die um rand(i, 51). Beachten Sie rand(i, 51), dass Sie NICHT benötigen rand(1, 51). Das wird nicht sicherstellen, dass jede Karte zufällig ist.
3. Zurücksetzen deck[0]auf 0. Jetzt wird das gesamte Deck bis auf die erste Karte gemischt, also tauschen Sie deck[0]mit deck[rand(0, 51)]und Sie sind fertig.

C # -Version:

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

Javascript-Version:

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

... wo swap(a, b)tauscht deck[a]mit deck[b].

Ruby, eine Zeile

Wird dies als Betrug angesehen? Es sollte so zufällig sein, wie es nur geht.

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

(Rubys randMethode nimmt nur ein Argument und erzeugt dann eine Zahl n, so dass 0 <= Zahl <Argument.)

Zusätzlich - ähnlich wie die Perl-Lösung von Sogart, aber meines Wissens leidet es nicht unter dem Problem:

deck = deck.sort_by{rand}

Rubys sort_by unterscheidet sich von sort - es generiert zuerst die Liste der Werte, nach denen das Array sortiert werden soll, und sortiert sie dann erst danach. Es ist schneller, wenn es teuer ist, die Eigenschaft zu finden, nach der wir sortieren, in allen anderen Fällen etwas langsamer. Es ist auch im Codegolf nützlich: P

JavaScript

Hinweis: diese Lösung ist technisch nicht korrekt, da es einen zweiten Parameter iin dem Aufruf von verwendet shuffle, der als eine externe Variable zählt.

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

Mit anrufen shuffle(deck,52)

Ein vollständiges Arbeitsbeispiel (musste swapleicht modifiziert werden, da es in JavaScript keine Pass-by-Reference von Ints gibt):

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

Vermeidet, Elemente mit sich selbst zu tauschen, muss also zweimal aufgerufen werden, um zufällig zu sein.

D

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..$];
    }
}

Eine andere Perl-Lösung, die tatsächlich eine gleichmäßig verteilte Ausgabe erzeugt:

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

say join " ", shuffle_integers 1 .. 52;

Diese Lösung verwendet Perls rand, die eine Zufallszahl x im Bereich von 0 ≤ x <1 zurückgeben. Sie addiert eine solche Zufallszahl zu jeder Ganzzahl in der Eingabe, sortiert die Zahlen nach ihren Bruchteilen und entfernt diese Bruchteile schließlich wieder .

(Ich glaube , dass die Verwendung der speziellen Variablen $_, $aund $bfällt in den Geist der Herausforderung, denn die sind , wie Perl die Eingabe geht auf mapund sort, und sie sind nicht für andere Zwecke im Code verwendet. Auf jeden Fall glaube ich, Sie sind tatsächlich Aliase zu den Eingabewerten und keine unabhängigen Kopien. Dies ist jedoch kein direktes Shuffle. Beide mapund sorterstellen Kopien der Eingabe auf dem Stapel.)

Java

Ich bin überrascht, dass niemand das Offensichtliche gesagt hat: (Ich gehe davon aus, dass Swap (x, x) nichts tut.

    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, es kann kürzer sein:

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

}

Burleske

Was Sie tatsächlich verlangen, ist eine zufällige Permutation einer Liste von ganzen Zahlen? r@wird uns alle Permutationen geben, und wir wählen nur eine zufällige.

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

Da wir echte Zufälligkeit benötigen, ist etwas, was Burlesque nicht kann, da Burlesque keine E / A-Funktionalität hat, die Sie benötigen, um eine Quelle für Zufälligkeit über STDIN bereitzustellen.

Das ist wahrscheinlich etwas, das ich in einer späteren Version korrigieren werde (dh beim Start einen zufälligen Startwert generieren und auf den sekundären Stapel oder ähnliches verschieben, aber der Burlesque-Interpreter selbst hat keine E / A).

Javascript

Ich bin nicht sicher, ob es sich um "Betrug" handelt, aber meine Lösung verwendet das native lokale Array der Argumente einer Funktion. Ich habe meine selbst erstellten Funktionen von rand() swap()und eingebunden filldeck(). Interessanterweise sollte dies mit einem Deck jeder Größe funktionieren.

    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

Missbrauchsfunktion time, mit der gemessen wird, wie viel Zeit ein Skript benötigt, aber auch als Schleifenmechanismus verwendet werden kann, ohne dass Variablen deklariert werden.

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

Probieren Sie es online!

Perl - Dies ist kein richtiger Shuffle, wie in den Kommentaren erklärt!

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

Ich glaube, ich habe nichts als Swap usw. verwendet. Wurde das als Teil des Problems benötigt?

JavaScript 4 Zeilen

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

Ursprüngliche Antwort, die nicht zufällig genug war. Es wurde nicht garantiert, dass der Tausch jeden Gegenstand im Deck berührt.

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