Celem tej układanki jest wzięcie talii 52 kart i przetasowanie jej tak, aby każda karta znajdowała się w losowej pozycji.

Dany:

• Tablica złożona deckz 52 różnych liczb całkowitych reprezentujących karty. Po uruchomieniu deckzawiera dokładnie jedną kartę w nieznanej kolejności.
• Funkcja, int rand(min, max)która zwraca losową liczbę całkowitą między liczbami całkowitymi mini maxwłącznie. Możesz założyć, że ta funkcja jest naprawdę losowa.
• Funkcja, void swap(x, y)która zamienia dwie karty w talii. Jeśli zadzwonisz swap(x, y), karty na pozycjach xi yzamieniają się miejscami.

Gdy:

• Wywołania programu shuffle()(albo shuffle(deck)albo deck.shuffle()albo jednak implementacja lubi działać),

Następnie:

• deck powinien zawierać dokładnie jedną z każdej karty w idealnie losowej kolejności.

The Catch:

Nie możesz zadeklarować żadnych zmiennych. Dzwoń swapi randile chcesz, ale nie możesz zadeklarować własnych zmiennych. Obejmuje to forliczniki pętli - nawet niejawne, takie jak w foreach.

Wyjaśnienia:

• Możesz zmienić drobne szczegóły w celu dopasowania do wybranego języka. Na przykład możesz napisać, swapaby zamienić dwie liczby całkowite przez odniesienie. Zmiany powinny polegać na ułatwieniu pracy z Twoim językiem, a nie na ułatwieniu układanki.
• deck może być zmienną globalną lub możesz przyjąć ją jako parametr.
• Możesz zrobić wszystko, co chcesz deck, ale nie możesz zmienić jego długości.
• Twoje karty mogą mieć numery 0-51, 1-52 lub cokolwiek innego.
• Możesz napisać to w dowolnym języku, ale bez oszustwa dzięki wbudowanej shufflefunkcji języka .
• Tak, możesz napisać tę samą linię 52 razy. Nikt nie będzie pod wrażeniem.
• Czas wykonania nie ma znaczenia, ale prawdziwa przypadkowość ma znaczenie.
• To nie jest tak naprawdę kod golfowy, ale możesz zminimalizować / zaciemnić kod.

Edycja: Kod Boilerplate i wizualizator

Jeśli korzystasz z .NET lub JavaScript, oto kod testowy, który może Ci się przydać:

JavaScript:

• Szybki i brudny wizualizator JavaScript ze źródłem CoffeeScript: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
• Wersja do uruchomienia (wystarczy wkleić w swojej shuffle()funkcji): http://jsfiddle.net/4zxjmy42/

DO#:

• Wizualizator ASP.NET z C # codebehind: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
• Stub za pomocą tylko swapi randnarzędziowych metod: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41

Ten kod sortuje i tasuje talię kilka tysięcy razy i wykonuje podstawowe testy poprawności poczytalności: Dla każdego losowania sprawdza, czy w talii są dokładnie 52 karty bez powtórzeń. Następnie wizualizator wykreśla częstotliwość każdej karty kończącej się w każdym miejscu w talii, wyświetlając mapę cieplną w skali szarości.

Wyjście wizualizatora powinno wyglądać jak śnieg bez widocznego wzoru. Oczywiście nie może udowodnić prawdziwej przypadkowości, ale jest to szybki i łatwy sposób sprawdzenia na miejscu. Polecam użycie tego lub czegoś podobnego, ponieważ pewne błędy w algorytmie tasowania prowadzą do bardzo rozpoznawalnych wzorców na wyjściu. Oto przykład danych wyjściowych z dwóch implementacji, jednej ze wspólną wadą:

Błędna wersja częściowo tasuje talię, więc może wyglądać dobrze, jeśli sprawdzisz tablicę ręcznie. Wizualizator ułatwia zauważenie wzoru.

JavaScript

Wierzę, że jest to zamierzona forma rozwiązania, używam karty w pozycji 0, aby śledzić postęp, tylko tasując karty, które zostały już użyte jako licznik, osiąga to standard 52! permutacje z idealnie równym rozkładem. Procedura jest skomplikowana z powodu zamiany XOR, która nie pozwala na zamianę samego elementu.

Edycja: Wbudowałem sortowanie, które sortuje każdy element na miejscu tuż przed jego użyciem, umożliwiając w ten sposób pracę z nieposortowaną tablicą. Porzuciłem również wywołanie rekurencyjne na korzyść pętli 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

Oto implementacja bez punktów. Brak zmiennych, parametrów formalnych lub wyraźnej rekurencji. Kiedyś lambdabot „s @pl(«bez sensu»), funkcja refactoring całkiem sporo.

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]

Oto moja procedura testowa, aby upewnić się, że liczby były równomiernie rozmieszczone:

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

Oto oryginalny algorytm:

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

jot

Ignorowanie tej talii jest zmienne, jest oczywiste ...

52 ? 52

Oczywiście, jeśli naprawdę potrzebujesz funkcji, jest taka, która zadziała, nawet jeśli zapomnisz usunąć jokery (lub spróbować przetasować coś innego niż karty).

{~ (# ? #)

Po to aby...

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

Prawdopodobnie jest to poza intencją pytania, które polegałoby na samodzielnym wykonaniu losowania z rand ( ?). Mogę to zrobić później, kiedy nie powinienem pracować.

Wyjaśnienie

Wyjaśnienie 52 ? 52:

• x ? y jest x losowymi unikalnymi przedmiotami od y.

Wyjaśnienie {~ (# ? #)jest trudniejsze ze względu na widelce i haki . Zasadniczo jest to to samo shuffle =: 3 : '((# y) ? (# y)) { y', co, które ma jeden domyślny argument ( y).

• # y podaje długość y
• To daje 52? 52 jak poprzednio, co jest losową permutacją 0..51
• x { y oznacza element yw indeksie x lub (w tym przypadku) elementy w indeksach w x.
• To pozwala tasować to, co jest przekazywane, nie tylko liczby całkowite.

Zobacz J Słownictwo, aby uzyskać szczegółowe informacje na temat operatorów, chociaż składnia i semantyka są dość skomplikowane z powodu programowania rangowego i milczącego.

Pyton

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

Korzystanie z reprezentacji czynnikowej

W reprezentacji czynnikowej permutacji element i przyjmuje wartości od 0 do Ni. Tak więc przypadkowa permutacja dotyczy tylko rand(0,i)każdego Ni.

W J:

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

gdzie ? xjest rand(0,x-1)i |.>:i.52jest52 51 ... 1

Następnie, jeśli ajest wartość Ith factoradic robimy swap: swap(deck[i], deck[i+a]). Lista par do wymiany to:

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

Zamiana, której będziemy używać, działa w następujący sposób:

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

Nie jest to tak naprawdę „odniesienie”, ale w J. nie ma żadnych rzeczywistych funkcji

Użyjemy długości talii ( #deck), aby uniknąć użycia stałej.

Kompletny program w 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

DO#

Oto moja własna odpowiedź oparta na algorytmie Fisher-Yatesa . Powinien dać ci idealny los, jeśli generator liczb losowych jest wystarczająco dobry.

Angielska wersja:

1. Wielokrotnie zamieniaj kartę na at deck[0]at deck[v], gdzie vjest wartość nominalna karty wdeck[0] . Powtarzaj do v == 0. To częściowo uporządkuje talię, ale to nie ma znaczenia. Wiesz już, że Karta 0 znajduje się z przodu talii, co oznacza, że ​​możesz ukraść to miejsce w tablicy i użyć go jako licznika pętli. Jest to kluczowe „oszustwo” dla problemu zmiennych lokalnych.
2. Zaczynając od pozycji 1 (druga karta w talii), zamień kartę na i z rand(i, 51). Zauważ, że potrzebujesz rand(i, 51), NIE rand(1, 51) . To nie gwarantuje, że każda karta jest losowa.
3. Ustaw deck[0]z powrotem do 0. Teraz cała talia jest tasuje wyjątkiem pierwszej karcie, więc zamiana deck[0]z deck[rand(0, 51)]i gotowe.

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

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

... gdzie swap(a, b)zamienia się deck[a]z deck[b].

Ruby, jedna linia

Czy to jest uważane za oszukiwanie? Powinno być tak losowe, jak to możliwe.

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

(Ruby's rand Metoda przyjmuje tylko jeden argument, a następnie generuje liczbę n taką, że 0 <= liczba <argument.)

Dodatkowo - podobny do rozwiązania Perla firmy sogart, ale o ile wiem, nie ma problemu:

deck = deck.sort_by{rand}

Ruby sort_by różni się od sortowania - najpierw generuje listę wartości do posortowania tablicy, a dopiero potem sortuje ją według nich. Szybciej jest, gdy znalezienie nieruchomości, którą sortujemy, jest drogie, nieco wolniejsze we wszystkich innych przypadkach. Jest także przydatny w golfie kodowym: P

JavaScript

UWAGA: To rozwiązanie jest technicznie niepoprawne, ponieważ wykorzystuje drugi parametr iw wywołaniu shuffle, który liczy się jako zmienna zewnętrzna.

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

Zadzwoń z shuffle(deck,52)

Kompletny działający przykład (musiałem swapnieznacznie zmodyfikować, ponieważ w JavaScript nie ma żadnego przekazu referencyjnego):

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

Unika zamiany elementów ze sobą, więc musi zadzwonić dwa razy, aby być losowym.

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

Kolejne rozwiązanie Perla, które faktycznie wytwarza równomiernie rozłożone wyjście:

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

say join " ", shuffle_integers 1 .. 52;

To rozwiązanie wykorzystuje Perla rand, który zwraca liczbę losową x z zakresu 0 ≤ x <1. Dodaje taką liczbę losową do każdej liczby całkowitej na wejściu, sortuje liczby według ich części ułamkowych, a na koniec usuwa te części ułamkowe ponownie .

(Wierzę, że użycie specjalnych zmiennych $_, $ai$b mieści się w duchu wyzwanie, ponieważ te są jak Perl przechodzi wejście do mapi sort, i nie są one wykorzystywane do innych celów w kodzie. W każdym razie, uważam, oni faktycznie aliasy do wartości wejściowych, a nie niezależne kopie to nie jest rzeczywiście losowe w miejscu, choć;. zarówno mapi sorttworzenia kopii wejścia na stosie).

Jawa

Dziwi mnie, że nikt nie stwierdził oczywistości: (Zakładam, że zamiana (x, x) nic nie robi.

    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, może być krótszy:

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

}

Groteska

To, o co właściwie prosisz, to losowa permutacja listy liczb całkowitych? r@da nam wszystkie permutacje, a my wybieramy losową.

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

Ponieważ potrzebujemy prawdziwej losowości, coś, czego Burlesque nie jest w stanie zrobić, ponieważ Burlesque nie ma funkcji We / Wy, musisz zapewnić jakieś źródło losowości za pośrednictwem STDIN.

Prawdopodobnie jest to coś, co naprawię w późniejszej wersji (tj. Wygeneruję losowe ziarno przy starcie i wypchnę go na drugi stos lub coś w tym rodzaju, ale sam Burlesque Interpreter nie ma I / O).

JavaScript

Nie jestem pewien, czy to „oszustwo”, ale moje rozwiązanie wykorzystuje natywną lokalną tablicę argumentów funkcji. Zawarłem moje samodzielnie wykonane funkcje rand() swap()i filldeck(). Co ciekawe, powinno to działać z talią dowolnego rozmiaru.

    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 bajty

Nadużywanie timefunkcji, która służy do pomiaru czasu, jaki skrypt wykonuje, ale może również służyć jako mechanizm zapętlający bez deklarowania żadnych zmiennych.

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

Wypróbuj online!

perl - nie jest to właściwe tasowanie, jak wyjaśniono w komentarzach!

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

Myślę, że nie użyłem niczego jako zamiany itp. Czy to było potrzebne jako część problemu?

JavaScript 4 linie

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

Oryginalna odpowiedź, która nie była wystarczająco losowa. Zamiana nie gwarantowała dotknięcia każdego przedmiotu w talii.

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