Random Golf of the Day # 1: Shuffle an Array

35

O serii

Będę prowadził serię golfowych wyzwań związanych z przypadkowością. Będzie to w zasadzie 9-dołkowe pole golfowe , ale rozłożone na kilka pytań. Możesz brać udział w każdym wyzwaniu indywidualnie, jakby to było normalne pytanie.

Będę jednak utrzymywać tabelę wyników we wszystkich wyzwaniach. Serial obejmie 9 wyzwań (na razie), jedno publikowane co kilka dni. Każdy użytkownik, który bierze udział we wszystkich 9 wyzwaniach, może wygrać całą serię. Ich ogólny wynik to suma ich najkrótszych zgłoszeń na każde wyzwanie (więc jeśli odpowiesz dwukrotnie na wyzwanie, tylko lepsza odpowiedź jest liczona do wyniku). Jeśli ktokolwiek będzie zajmował najwyższe miejsce w ogólnej tabeli liderów przez 28 dni , przyznam mu nagrodę w wysokości 500 powtórzeń .

Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .

Hole 1: Shuffle an Array

Pierwsze zadanie jest dość proste: biorąc pod uwagę niepustą tablicę liczb całkowitych, losowo ją potasuj. Istnieje jednak kilka zasad:

  • Każda możliwa permutacja musi zostać zwrócona z takim samym prawdopodobieństwem (dlatego losowanie powinno mieć jednolity rozkład). Możesz sprawdzić, czy twój algorytm jest jednorodny / bezstronny, implementując go w JavaScript w Will it Shuffle , co wytworzy matrycę tendencyjności - wynik powinien wyglądać tak jednolicie, jak wbudowane Fisher-Yates lub sortować (kolejność losowa) .
  • Nie wolno używać żadnej wbudowanej lub innej firmy metody tasowania tablicy lub generowania losowej permutacji (lub wyliczenia wszystkich permutacji). W szczególności jedyną wbudowaną funkcją losową, której możesz użyć, jest uzyskanie pojedynczej liczby losowej na raz . Państwo może założyć, że każdy wbudowaną losowych przebiegów metoda numer w czasie O (1) i jest idealnie równomierne na wymaganym przedziale (w sensie matematycznym - można zignorować szczegóły reprezentacji zmiennoprzecinkowej tutaj). Jeśli twój język pozwala ci uzyskać listę m liczb losowych naraz, możesz skorzystać z tej funkcji, pod warunkiem, że m liczb jest od siebie niezależnych i policzysz je jako O (m).
  • Implementacja nie może przekraczać złożoności czasowej O (N) , gdzie N jest rozmiarem tablicy, która ma być tasowana. Na przykład nie można „sortować według liczb losowych”.
  • Możesz albo przetasować tablicę na miejscu, albo utworzyć nową tablicę (w takim przypadku stara tablica może zostać zmodyfikowana w dowolny sposób).

Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, argumentu funkcji lub pytania i wygenerować dane wyjściowe za pomocą wartości zwracanej lub drukując do STDOUT (lub najbliższej alternatywy). Jeśli napiszesz funkcję, która przetasowuje tablicę w miejscu, nie musisz jej oczywiście zwracać (pod warunkiem, że Twój język pozwala na dostęp do zmodyfikowanej tablicy po powrocie funkcji).

Dane wejściowe i wyjściowe mogą być w dowolnym dogodnym formacie listy lub ciągu, ale muszą obsługiwać dowolne liczby całkowite z zakresu -2 31 ≤ x <2 31 . W zasadzie, Twój kod powinien działać dla tablic do długości 2 do 31 , choć niekoniecznie muszą zmieścić się w pamięci lub kompletne w rozsądnym czasie. (Po prostu nie chcę widzieć dowolnych limitów wielkości pętli kodu twardego itp.)

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).

Tabela liderów

Poniższy fragment wygeneruje tabelę wyników we wszystkich wyzwaniach serii.

Aby mieć pewność, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).

Martin Ender
źródło
7
Jestem rozczarowany, że nie możemy być „sprytni” i używać funkcji bibliotecznych innych niż „uzyskać liczbę losową” . Czy chcemy spojrzeć na kolejne 69 implementacji tasowania Fisher-Yates? Rozważ usunięcie tej reguły w przyszłych zadaniach. Ponadto, dlaczego ograniczenie złożoności czasu? Proszę rozważyć złagodzenie go do co najmniej O (n ^ 2); Myślę też, że ktoś może znaleźć szczególnie golfową implementację, jeśli pozwolisz O (n!).
anatolyg
7
@anatolyg Usunięcie ograniczeń oznacza, że ​​każda odpowiedź jest sortby(random)(powodem ograniczenia czasowego) lub po prostu .shuffle()(powodem ograniczenia wbudowanego), co moim zdaniem jest o wiele mniej sprytne niż konieczność implementacji Fisher-Yatesa lub innej podejście.
Martin Ender,
1
Jeśli tasowanie jest na miejscu, czy funkcja musi zwrócić tablicę, czy wystarczy, że zostanie zmodyfikowana? Czy mogę napisać funkcję shuffle(array)zamiast newArray=shuffle(array)?
Geobity
1
@ Bakuriu Twierdzenie, że możesz sortować w czasie liniowym, jeśli liczby są ustalone, przypomina trochę twierdzenie, że możesz zrobić wszystko w O (1), jeśli rozmiary wejściowe są ustalone. Istotnym ograniczeniem są również tablice o stałym rozmiarze, a nie liczby całkowite o stałym rozmiarze - ponieważ rozmiar tablicy określa, jak duże powinny być liczby losowe. W każdym razie ograniczenie złożoności czasu dotyczy oczywiście ogólnego algorytmu, który wdrażasz, podczas gdy ograniczenia wielkości wejściowych są na miejscu, więc nie musisz używać liczb całkowitych o dowolnej dokładności, jeśli Twój język nie używa ich po wyjęciu z pudełka. .
Martin Ender
2
Dlaczego rozwiązanie Adáma pojawia się jako 43319 bajtów, gdy w rzeczywistości jest to 14?
Boboback

Odpowiedzi:

20

Dyalog APL, 25 24 bajtów

Po pierwsze dla rozwiązania składającego się z 25 znaków: 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[⍵]

Po niektórych przekształceniach równoważności na powyższym:

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

możemy pozbyć się zadania i←i zapisać postać:

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

ngn
źródło
3
... umysł. nadęty.
danwyand
1
język, który muszę czytać od prawej do lewej? łał!
Luminous
5
@Luminous, jak to często bywa z notacją matematyczną: sin cos ln sqrt x
ngn
4
@ngn, kiedy ujmujesz to w ten sposób, sprawia, że ​​mój poprzedni komentarz wygląda na śmiech. ha.
Luminous
5
@ronalchn jest 8-bitowe kodowania dla APL, jak to jeden lub tym drugim; Słyszałem, że Dyalog używa jednego z nich, jako alternatywy dla Unicode.
anatolyg
12

80386 kod maszynowy, 44 24 bajtów

Hexdump kodu:

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

Dzięki FUZxxl, który zasugerował użycie rdrandinstrukcji.

Oto kod źródłowy (może zostać skompilowany przez 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;
    }
}

Kolejna implementacja Fisher-Yates. Większość golfa została osiągnięta poprzez przekazanie parametrów do rejestrów.

anatolig
źródło
1
Mógłbyś także użyć rdranddo gówna i chichotów.
FUZxxl
@FUZxxl Zupełnie o tym zapomniałem! Szkoda, że ​​usuwa najciekawszą część mojej odpowiedzi ...
anatolyg
9

Java, 88 101

Podstawowym tasowaniem jest Fisher-Yates. Mam wrażenie, że będzie tu używany dość często, ponieważ jest szybki i łatwy do wdrożenia. Jest tu trochę wkuwania pętli / zadań, ale tak naprawdę nie ma zbyt wiele do golfa; z natury jest krótki.

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

Z pewnymi podziałami linii:

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

To tasuje w miejscu, modyfikując oryginalną tablicę s[]. Program testowy:

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--;}
}
Geobity
źródło
1
Nie, wyzwanie stwierdza, że ​​można założyć, że „ jest idealnie jednolity w żądanym zakresie ”. Wymagany zakres Math.random()ma rozmiar, który jest potęgą dwóch, więc nie spełnia specyfikacji.
Peter Taylor
1
Interpretacje @PeterTaylor Jan i Geobits są rzeczywiście tym, jak zamierzałem, zasadą - nie musisz się martwić o rzeczywistą długość cyklu swojego PRNG.
Martin Ender
1
@ MartinBüttner długość cyklu nie jest tutaj problemem - jest to objęte twoją regułą. Grubość pływaków jest.
John Dvorak
3
@TheBestOne To jeden bajt krótszy niż jedyne obecnie opublikowane rozwiązanie dla python;)
Geobits
1
Nigdy więcej! : D
Sp3000,
8

Python 2, 86 bajtów

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

Jest to funkcja, która przetasowuje tablicę w miejscu bez zwracania jej, wykorzystując prostą implementację tasowania Fisher-Yates . Pobieranie losowych liczb z Pythona jest drogie ...

Dzięki @xnor i @colevk za wskazówki.

Sp3000
źródło
To wyrażenie zakresu wydaje się dość niewygodne. Z pewnością krócej odliczasz ręcznie jako while i:i-=1;...?
xnor
@xnor Tak, to jest - dzięki za to. Ciągle zapominam, że jest to whilezwykle krótsze niż w forprzypadku takich rzeczy ...
Sp3000
1
Awww ... teraz moja odpowiedź Java nie bije tego. Byłem bardzo szczęśliwy przez bardzo krótki czas :(
Geobits
Możesz zapisać kolejne 2 bajty, wykonując i=len(L)i umieszczając zmniejszenie na początku pętli while.
colevk
8

J, 45 44 znaków

To było trudne.

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

Oto wyjaśnienie:

  1. # y: The tally of y, czyli liczba elementów wy .
  2. ?@# y: Liczba losowa równomiernie rozmieszczona w zakresie od 1do(#y)-1 .
  3. x { y: Pozycja z y indeksu x.
  4. (<<<x) { y: Wszystkie elementy oprócz pozycji o indeksie xw y.
  5. x , y: y dołączono do x.
  6. x ({ , <^:3@[ { ]) y: Pozycja w indeksie xw y, a następnie wszystkie inne pozycje.
  7. (?@# ({ , <^:3@[ { ]) ]) yLosowo z y, a następnie wszystkie inne przedmioty.
  8. x {. y: Pierwsze xelementy zaczerpnięte z y.
  9. x }. y: Pierwsze xegzemplarze spadł zy .
  10. x ({. , }.) y: Pierwsze xelementy wzięte z y, potem pierwsze xegzemplarze spadł zy
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Pierwsze xelementy wzięte z y, a następnie pierwsze xelementy yprzetworzone jak w numerze 7.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: To samo z kroplą wciągniętą, aby uratować jedną postać.
  13. u/ y: u wstawiony między pozycje z y.
  14. < y: y zapakowane .
  15. <"0 y: Każda pozycja w y pudełku .
  16. i. y: liczby całkowite od 0do y - 1.
  17. i.@# y: liczby całkowite od 0do (#y) - 1.
  18. (<"0@i.@# , <) y: Całkowite od 0do (#y) - 1siebie ramkach , a następnie yw jednej obudowie. Jest to konieczne, ponieważ tablice w J są jednolite. Pudełko ukrywa kształt zawartości.
  19. x u&v y: jak (v x) u (v y).
  20. > y: y otwarty , to znaczy bez pudełka.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y fraza z liczby 12 zastosowana do jej nieopakowanych argumentów.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ yzdanie z numeru 21 wstawione między pozycje z y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) yzwrot z numeru 22 zastosowany do wyniku zdania z numeru 18 lub jednolita permutacja pozycji z y.
FUZxxl
źródło
1
Po prostu nie mogę rozróżnić wszystkich nawiasów. A potrójne boksowanie <@<@<@[jest również tajemnicą ... Czekam na wyjaśnienia. :)
randomra
2
Gdy zostanie to wyjaśnione, być może z większym prawdopodobieństwem poprę tę odpowiedź ;-)
John Dvorak
@randomra Proszę bardzo.
FUZxxl
@JanDvorak Czy wyjaśnienie jest satysfakcjonujące?
FUZxxl,
Świetne wyjaśnienie! Nie wiedziałem o wszystkich zastosowaniach from( {) w pudełkach . I naprawdę podoba mi się &>/sztuczka polegająca na manipulowaniu listą. Jestem pewien, że mogłem go użyć kilka razy wcześniej.
randomra
5

Pyth, 25 bajtów

Sprawdź to tutaj.

Kolejna implementacja Fisher-Yates. Jest zasadniczo taki sam, jak @ Sp3000 rozwiązanie python, tylko w pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Dzięki @Jakube za sztuczkę wymiany

<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
źródło
Możesz zapisać dwa bajty, łącząc te dwa przypisania do listy: `XXQN @ QKKJ` zamiast` XQN @ QK XQKJ`.
Jakube,
@Jakube dzięki za wskazówkę. Wiedziałem, że musiał istnieć sposób na zamianę wartości na liście, i to jest naprawdę sprytne. Powinieneś dodać go do listy wskazówek.
Maltysen
4

Perl, 68 56 44

Podobnie jak wiele innych rozwiązań, wykorzystuje Fisher-Yates algorytm .

Za pomocą komentarza nutki zapisywanych jest 12 znaków przy użyciu $_zamiast $ii wykonywania operacji na indeksach tablicowych.

44:

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

56:

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

To jest mój pierwszy codegolf.

Bonsaigin
źródło
Niezły początek, nie wiedziałem, że możesz użyć @_[...]jako takiej wartości. Można zagrać w golfa dalej sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}.
nutki
3

C, 63 61 60 bajtów

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

Tylko prosta implementacja Fischera-Yatesa, która sortuje podaną tablicę na miejscu. Kompiluje i łączy się doskonale z kompilatorem Visual Studio (vs2013, nie testowałem innych wersji) i kompilatorem Intel. Ładnie wyglądająca sygnatura funkcji tos(int array[], int length) . Jestem pod wrażeniem, że pokonałem Pythona i Ruby.

Zakłada się, że srand()jest wywoływany, a rand () jest poprawnie zaimplementowany, ale uważam, że ta reguła pozwala na to:

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

Ładnie sformatowana wersja:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
pseudonim117
źródło
Myślę, że wystarczy utworzyć nagłówek funkcji s(a,m)*a{, ale nie jestem pewien i nie chcę też testować. Możesz zrobić xor-swap, jak w a[i]^=a[m]^=a[i]^=a[m]. Pozwala to również uniknąć konieczności deklarowania t.
FUZxxl,
@FUZxxl I believe an xor swap causes problems if i==m.
Geobits
@Geobits indeed. I missed that possibility.
FUZxxl
Chciałem tylko dowiedzieć się, dlaczego to nie działa ... powinienem to zapamiętać. Potrzebuję też s(a,m)int*astudia wizualnego i kompilatora Intel. Nie instaluj gcc ani clang do testowania, ale zakładam, że będą również narzekać.
pseudonim
Jest to imponująco gra w golfa. Po wypróbowaniu wielu modyfikacji, które niczego nie zapisały, udało mi się znaleźć sposób na uratowanie 2 postaci. Jeśli zmienisz kolejność wymiany, tak aby stała się pierwsza instrukcja wymiany t=a[i], możesz przenieść i=rand()%m--instrukcję do wewnątrz jako indeks tablicy.
Runer112
3

Oktawa, 88 77 bajtów

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

Yet another Fisher-Yates implementation... Should be fairly straightforward if I add the usual line returns and spacing:

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

The "end" keywords really kill the golf score here, unfortunately. Hey, I can use "end" instead of "endfor" and "endfunction"!

dcsohl
źródło
1
Just FYI, the "bytes" isn't really required by the code, it just makes sure there is a headline, which contains a comma (to separate the language) and at least one number after the comma, and then just chooses the last number that isn't crossed out. Having "bytes" in there is still nice though. ;)
Martin Ender
1
You could save 1 byte by using numel instead of lenght. As a bonus your program would also work with 2-D arrays aka matrices ;)
paul.oderso
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--;};

It's a lambda taking int[] and returning void. My first attempt seemed not very interesting, so I decided to have it exit by throwing an exception.

Test program:

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
źródło
1
Isn't it cheating to use a lambda to get around having to write a function signature, when you have to supply a delegate in order to use the lambda anywhere? Also... can't you drop the parentheses around Math.random()?
Rawling
1
@Rawling You could vote in this meta question. Currently, there are 9 votes in favor of lambdas, and 0 against. Yes, the parentheses can be removed.
feersum
Huh, if there's a meta post and a so-far-consensus then fire away. (And enjoy the two-lower golf score on me :p)
Rawling
3
I think, it's unfair for function to stop by exception in a normal case, is it?
Qwertiy
1
@Qwertiy To each his own... You think it's unfair, I think it's great.
feersum
2

Golflua, 37

How to run Golflua?

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

The input is provided as a table in the variable X. The table is shuffled in place.

Example usage:

> 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
źródło
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}

This is a straightforward implementation of the Fisher-Yates shuffle. The R function sample draws a simple random sample of a given size from a given vector with equal probability. Here we're drawing a random sample of size 1 at each iteration from the integers i, ..., n. As stated in the question, this can be assumed to be O(1), so in all this implementation should be O(N).

Alex A.
źródło
2

Matlab, 67

Also implementing Fisher-Yates.

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

I thought it was too bad I could not use Matlab's randperm function. But after some fiddling around, I thought I may look at the source of randperm to see how it is done, and I was astonished to see that there was just one line: [~,p] = sort(rand(1,n)) =)

flawr
źródło
2

Perl, 44

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

Another perl in 44 characters. Example use:

@x=(1..9);f(@x);print@x
nutki
źródło
2

Mathematica, 82 90 83 93 bytes

Note: This variation the Fisher-Yates shuffle is actually Martin Büttner's solution, with some code paring by alephalpha. s is the input array. Nothing fancy-smancy, but sometimes the simple things are the most elusive.

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
źródło
You can use Do here. It's shorter than 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}

Input (as lambda function):

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

Output:

[2, 1, 4, 3, 5]
Zero Fiber
źródło
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

Source for byte count

Ypnypn
źródło
1
You're missing the End.
lirtosiast
2

K, 31 chars

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

Not quite as short as the one I put up before (which got disqualified)...oh well.

It's a basic Fisher-Yates shuffle. This was built with lots of help from the Kona mailing list.

kirbyfan64sos
źródło
2

JavaScript (ES6), 66

This function shuffles the array in place. It also returns a byproduct array that is NOT the shuffled output and must not be considered.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)
edc65
źródło
2

MATL, 16 bytes

XH`HnYr&)XHxvHHn

Try it online!

Fisher-Yates in MATL. Almost a third of this program is devoted to the letter H, which corresponds to the clipboard function in MATL.

Basically, H stores the unused items from the input, while the stack keeps track of the shuffled list.

Sanchises
źródło
2

Japt, 12

rÈiMqZÄ Y}[]

Try it!

-10 (about half ;) thanks to @Shaggy!

I have been wanting to try out a golfing language, and the Japt interpreter had good documentation and a way to try things out in the browser.

Below is the strategy I took:

  • Reduce input seeding with an empty array
  • At each step, find a random slot to insert the current element
dana
źródło
1
Welcome to Japt, good to have you with us. I think this works for 9 bytes, using the same method. If the RNG isn't satisfactory, though, then try this instead.
Shaggy
@Shaggy - Thanks for the tips! :) I ended up using a slightly modified version of your 2nd solution. Since the 3rd parameter of the reduce function is an index, we already know the length.
dana
1

Javascript ES6, 69

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

It's Fisher–Yates.

PS: Can be tested in Firefox

Qwertiy
źródło
@MartinBüttner, removed it :)
Qwertiy
1

Pyth, 27 bytes

Test it here

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

This is an implementation of the incremental Fisher-Yates shuffle, mentioned second here.

isaacg
źródło
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

Another Fisher-Yates solution inspired by the algorithm at https://wiki.haskell.org/Random_shuffle.

s is a function which has signature: IOArray Int a -> IO [a]

Jmac
źródło
1

CJam - 30

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

Try it at http://cjam.aditsu.net/

Example input: [10 20 30 40 50]
Example output: 3020401050 (add a p at the end of the code for pretty printing)

If the code is allowed to take the input from the stack (like a function), then the first 2 characters can be removed, reducing the size to 28.

Explanation:

The code is longer than I hoped, due to the lack of a "swap" operator for arrays
(to be implemented later :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
źródło
As mentioned in the comments, I'm afraid this is invalid. At the very least _ is O(N) (inside an O(N) loop). Unfortunately, I don't see a way to work around that in CJam.
Martin Ender
Lists are handled like immutable objects, so duplication is just implemented as duplicating the reference. It's actually the t that kills it, as it can't mutate the list and now must create a copy.
Runer112
@MartinBüttner I was about to post the same thing as Runer112; yes there might be a problem with t, I'd like to improve it in future versions..
aditsu
So this code follows the spirit of the question, but not the "letter", due to internal language implementation issues.
aditsu
1

JavaScript (ES 6), 61

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

You can test it here by just adding a line that says shuffle = S (Firefox only).

core1024
źródło
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

Expects input as space separated numbers. I can remove the headers and observation numbers from the output if you would like, but otherwise this is shorter.

bmarks
źródło
What's _n in this?
Martin Ender
_n is the number of the current observation.
bmarks
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);}

Example usage: http://ideone.com/RqSMnZ

TheNumberOne
źródło
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
źródło
1
This is biased (see "swap (i <-> random)" on Will It Shuffle), but you can turn it into Fisher-Yates (which is unbiased) by replacing %x with %i.
Martin Ender