Цель этой головоломки состоит в том, чтобы взять колоду из 52 карт и перемешать ее, чтобы каждая карта находилась в случайном положении.

Данный:

• Массив deckиз 52 различных целых чисел, представляющих карты. При запуске deckсодержит ровно по одной каждой карточке в каком-то неизвестном порядке.
• Функция, int rand(min, max)которая возвращает случайное целое число между целыми числами minи maxвключительно. Вы можете предположить, что эта функция действительно случайна.
• Функция, void swap(x, y)которая меняет две карты в колоде. Если вы позвоните swap(x, y), карты на местах xи yпоменяются местами.

Когда:

• Программа вызывает shuffle()(или, shuffle(deck)или как deck.shuffle()вам нравится запускать вашу реализацию),

Потом:

• deck должен содержать ровно одну каждую карту в совершенно случайном порядке.

Поймать:

Вы не можете объявить какие-либо переменные. Вызовите swapи randсколько угодно, но вы не можете объявить свои собственные переменные. Это включает в себя forсчетчики циклов - даже неявные, как в foreach.

Разъяснения:

• Вы можете изменить мелкие детали в соответствии с выбранным вами языком. Например, вы можете написать swapдля переключения двух целых чисел по ссылке. Изменения должны быть сделаны, чтобы это работало с вашим языком, а не чтобы облегчить задачу.
• deck может быть глобальной переменной, или вы можете принять ее в качестве параметра.
• Вы можете делать с содержимым все, что хотите deck, но не можете изменять его длину.
• Ваши карты могут быть пронумерованы 0-51, 1-52 или как угодно.
• Вы можете написать это на любом языке, но без обмана с помощью встроенной shuffleфункции вашего языка .
• Да, вы можете написать одну и ту же строку 52 раза. Никто не будет впечатлен.
• Время выполнения не имеет значения, но истинная случайность имеет значение.
• Это на самом деле не гольф-код, но вы можете минимизировать / запутать ваш код.

Редактировать: код Boilerplate и визуализатор

Если вы использовали .NET или JavaScript, вот несколько тестовых кодов, которые вам могут пригодиться:

JavaScript:

• Быстрый и грязный визуализатор JavaScript с источником CoffeeScript: https://gist.github.com/JustinMorgan/3989752bdfd579291cca
• Запускаемая версия (просто вставьте в свою shuffle()функцию): http://jsfiddle.net/4zxjmy42/

C #:

• Визуализатор ASP.NET с кодом C #: https://gist.github.com/JustinMorgan/4b630446a43f28eb5559
• Заглушка с только swapи randполезными методами: https://gist.github.com/JustinMorgan/3bb4e6b058d70cc07d41

Этот код сортирует и перетасовывает колоду несколько тысяч раз и выполняет некоторое базовое тестирование работоспособности: для каждого перемешивания он проверяет, что в колоде находится ровно 52 карты без повторов. Затем визуализатор отображает частоту каждой карты в каждом месте колоды, отображая тепловую карту в оттенках серого.

Вывод визуализатора должен выглядеть как снег без видимого рисунка. Очевидно, что это не может доказать истинную случайность, но это быстрый и простой способ выборочной проверки. Я рекомендую использовать его или что-то подобное, потому что определенные ошибки в алгоритме тасования приводят к очень узнаваемым паттернам в выходных данных. Вот пример вывода из двух реализаций, одна с общим недостатком:

Неправильная версия частично перетасовывает колоду, поэтому может хорошо выглядеть, если вы изучили массив вручную. Визуализатор позволяет легче заметить шаблон.

JavaScript

Я считаю, что это предполагаемая форма решения, я использую карту в положении 0, чтобы отслеживать прогресс, только перетасовывая карты, которые уже использовались в качестве счетчика, это достигает стандартных 52! перестановки с идеально равным распределением. Процедура усложняется обменом XOR, не позволяющим заменить элемент самостоятельно.

Редактировать: я встроил сортировку, которая сортирует каждый элемент на месте непосредственно перед его использованием, что позволяет работать с несортированным массивом. Я также отбросил рекурсивный вызов в пользу цикла 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

Вот бессмысленная реализация. Нет переменных, формальных параметров или явной рекурсии. Я использовал lambdabot «s @pl(„бессмысленный“) рефакторинг функции совсем немного.

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]

Вот моя процедура тестирования, чтобы убедиться, что числа были распределены равномерно:

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

Вот оригинальный алгоритм:

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

Игнорирование этой колоды является переменной, есть очевидное ...

52 ? 52

Конечно, если вам действительно нужна функция, она есть, которая будет работать, даже если вы забудете удалить джокеров (или попытаетесь перетасовать что-то, кроме карт).

{~ (# ? #)

И что...

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

Вероятно, это выходит за рамки вопроса, заключающегося в том, чтобы реализовать случайное перемешивание из rand ( ?). Я мог бы сделать это позже, когда я не должен работать.

объяснение

Объяснение 52 ? 52 :

• x ? y х случайных уникальных предметов от у.

Объяснение {~ (# ? #)сложнее из-за вилок и крючков . По сути, это то же самое shuffle =: 3 : '((# y) ? (# y)) { y', что имеет один неявный аргумент (y ).

• # y дает длину у
• Это дает 52? 52, как и раньше, что является случайной перестановкой 0..51
• x { y это элемент y в индексе x или (в данном случае) элементы в индексах в x.
• Это позволяет вам перемешивать все, что передано, а не только целые числа.

Смотрите J Vocabulary для подробностей об операторах, хотя синтаксис и семантика довольно сложны из-за рангового и неявного программирования.

питон

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

Использование факторического представления

В факторическом представлении перестановки элемент i принимает значения от 0 до Ni. Так что случайная перестановка только rand(0,i)для каждого Ni.

В J:

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

где ? xесть rand(0,x-1)и |.>:i.52есть52 51 ... 1

Затем, если aэто значение Ith factoradic, мы делаем обмен: swap(deck[i], deck[i+a]). Список пар для обмена:

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

Обмен, который мы будем использовать, работает следующим образом:

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

Это не совсем «по ссылке», но в J. нет реальных функций.

Мы будем использовать length ( #deck), чтобы избежать использования константы.

Полная программа на 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 #

Вот мой собственный ответ, основанный на алгоритме Фишера-Йейтса . Должен дать вам идеальную случайность, если ваш генератор случайных чисел достаточно хорош.

Английская версия:

1. Неоднократно меняйте местами карту deck[0]с той deck[v], где vнаходится номинальная стоимость карты deck[0]. Повторять доv == 0 . Это будет частично сортировать колоду, но это не имеет значения. Теперь вы знаете, что карта 0 находится в передней части колоды, что означает, что вы можете украсть это пространство в массиве и использовать его в качестве счетчика циклов. Это ключевой «чит» для проблемы локальных переменных.
2. Начиная с позиции 1 (вторая карта в колоде), поменяйте карту на iс той, что в rand(i, 51). Обратите внимание, что вам нужно rand(i, 51), а не rand(1, 51) . Это не гарантирует, что каждая карта рандомизирована.
3. Установить deck[0]на 0. Теперь вся колода перемешивается для первой карты , за исключением, так свопа deck[0]с , deck[rand(0, 51)]и вы сделали.

Версия 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)]);
}

Версия 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));

... где swap(a, b)обмен deck[a]с deck[b].

Рубин, одна строка

Это считается обманом? Это должно быть настолько случайным, насколько это возможно.

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

( randМетод Руби принимает только один аргумент, а затем генерирует число n такое, что 0 <= число <аргумент.)

Дополнительно - похоже на Perl-решение sogart, но, насколько я знаю, оно не страдает от проблемы:

deck = deck.sort_by{rand}

Сортировка Ruby sort_by отличается от sort - сначала она генерирует список значений, по которым сортируется массив, и только затем сортирует его по ним. Быстрее найти свойство, по которому мы сортируем, быстрее, во всех остальных случаях - немного медленнее. Это также полезно в коде гольф: P

JavaScript

ПРИМЕЧАНИЕ. Технически это решение некорректно, поскольку iв вызове используется второй параметр shuffle, который считается внешней переменной.

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

Позвонить с shuffle(deck,52)

Полный рабочий пример (пришлось swapнемного изменить, потому что в 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] << " ";
}

Избегает обмена элементами между собой, поэтому должен вызываться дважды, чтобы быть случайным.

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

Другое решение Perl, которое фактически производит равномерно распределенный вывод:

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

say join " ", shuffle_integers 1 .. 52;

Это решение использует Perl rand, который возвращает случайное число x в диапазоне 0 ≤ x <1. Он добавляет такое случайное число к каждому целому числу на входе, сортирует числа по дробным частям и, наконец, удаляет эти дробные части снова ,

(Я считаю , что использование специальных переменных $_, $aи $bпадает в духе вызов, так как те , как Perl проходит вход в mapи sort, и они не используются для других целей , в коде. В любом случае, я считаю , они на самом деле псевдонимы для входных значений, а не независимые копии Это фактически не перетасовка на месте, хотя,. , как mapи sortсоздавать копии входа в стеке).

Джава

Я удивлен, что никто не указал очевидное: (Я предполагаю, что swap (x, x) ничего не делает.

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

ОК, хорошо, это может быть короче:

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

}

бурлеск

Что вы на самом деле просите, так это случайную перестановку списка целых чисел? r@даст нам все перестановки, и мы просто выберем случайную.

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

Поскольку нам нужна настоящая случайность, то, что Бурлеск не в состоянии сделать, потому что Бурлеск не имеет функциональных возможностей ввода / вывода, вам нужно было бы предоставить какой-то источник случайности через STDIN.

Это, вероятно, что-то, что я исправлю в более поздней версии (то есть создаю случайное начальное число при запуске и помещаю его во вторичный стек или что-то в этом роде, но сам Burlesque Interpreter не имеет ввода-вывода).

Javascript

Я не уверен, что это «обман», но мое решение использует собственный локальный массив аргументов функции. Я включил свои самодельные функции rand() swap()и filldeck(). Интересно отметить, что это должно работать с колодой любого размера.

    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 байта

Злоупотребления time функцией, которая служит для измерения того, сколько времени затрачивается на выполнение сценария, но также может служить циклическим механизмом без объявления каких-либо переменных.

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

Попробуйте онлайн!

Perl - это не правильное перемешивание, как описано в комментариях!

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

Я думаю, что я ничего не использовал в качестве подкачки и т. Д. Это было необходимо как часть проблемы?

JavaScript 4 строки

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

Оригинальный ответ, который не был достаточно случайным. Своп не гарантировал прикосновения к каждому предмету в колоде.

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