Zufälliges Golf des Tages Nr. 1: Ein Array mischen

35

Über die Serie

Ich werde eine kleine Reihe von Code-Golf-Herausforderungen durchführen, die sich um das Thema Zufälligkeit drehen. Dies wird im Grunde ein 9-Loch- Golfplatz sein , der sich jedoch über mehrere Fragen erstreckt. Sie können an jeder Herausforderung einzeln teilnehmen, als wäre es eine normale Frage.

Ich werde jedoch über alle Herausforderungen hinweg eine Rangliste führen. Die Serie wird (vorerst) über 9 Herausforderungen laufen, die alle paar Tage veröffentlicht werden. Jeder Benutzer, der an allen 9 Herausforderungen teilnimmt, hat Anspruch auf den Gewinn der gesamten Serie. Ihre Gesamtpunktzahl ist die Summe ihrer kürzesten Einsendungen bei jeder Herausforderung. Wenn Sie also zweimal auf eine Herausforderung antworten, wird nur die bessere Antwort für die Punktzahl gewertet. Wenn jemand 28 Tage lang den ersten Platz in dieser Rangliste belegt, werde ich ihm eine Prämie von 500 Wiederholungen gewähren .

Obwohl ich eine Menge Ideen für die Serie habe, sind die zukünftigen Herausforderungen noch nicht in Stein gemeißelt. Wenn Sie Vorschläge haben, teilen Sie mir dies bitte auf dem entsprechenden Sandbox-Post mit .

Loch 1: Mische ein Array

Die erste Aufgabe ist ziemlich einfach: Wenn Sie ein nicht leeres Array von Ganzzahlen haben, mischen Sie es nach dem Zufallsprinzip. Es gibt jedoch ein paar Regeln:

  • Jede mögliche Permutation muss mit der gleichen Wahrscheinlichkeit zurückgeführt werden (so die Shuffle eine gleichmäßige Verteilung haben soll). Sie können überprüfen, ob Ihr Algorithmus einheitlich / unparteiisch ist, indem Sie ihn in JavaScript auf Will it Shuffle implementieren. Dadurch wird eine Matrix der Verzerrungen erstellt. Das Ergebnis sollte so einheitlich aussehen wie die eingebauten Fisher-Yates oder die Sortierung (zufällige Reihenfolge) .
  • Sie dürfen keine integrierte Methode oder Methode eines Drittanbieters verwenden, um das Array zu mischen oder eine zufällige Permutation zu generieren (oder alle Permutationen aufzulisten). Insbesondere integrierte in dem einzigen Zufallsfunktion können Sie eine einzelne Zufallszahl zu einer Zeit bekommen . Sie können davon ausgehen, dass eine integrierte Zufallszahlenmethode in O (1) ausgeführt wird und über das angeforderte Intervall vollkommen einheitlich ist (mathematisch gesehen - Sie können hier Details der Gleitkommadarstellung ignorieren). Wenn Sie in Ihrer Sprache eine Liste mit m Zufallszahlen auf einmal erhalten können, können Sie diese Funktion verwenden, vorausgesetzt, die m Zahlen sind unabhängig voneinander und Sie zählen sie als O (m).
  • Ihre Implementierung darf eine zeitliche Komplexität von O (N) nicht überschreiten , wobei N die Größe des zu mischenden Arrays ist. Beispielsweise können Sie nicht nach Zufallszahlen sortieren.
  • Sie können das Array entweder an Ort und Stelle mischen oder ein neues Array erstellen (in diesem Fall kann das alte Array geändert werden, wie Sie möchten).

Sie können ein vollständiges Programm oder eine Funktion schreiben und Eingaben über STDIN, Befehlszeilenargument, Funktionsargument oder Eingabeaufforderung vornehmen und Ausgaben über Rückgabewerte oder durch Drucken an STDOUT (oder die nächstgelegene Alternative) erzeugen. Wenn Sie eine Funktion schreiben, die das Array an Ort und Stelle mischt, müssen Sie sie natürlich nicht zurückgeben (vorausgesetzt, Sie können in Ihrer Sprache nach der Rückkehr der Funktion auf das geänderte Array zugreifen).

Die Ein- und Ausgabe kann in einem beliebigen Listen- oder Zeichenfolgeformat erfolgen, muss jedoch beliebige Ganzzahlen im Bereich -2 31 ≤ x <2 31 unterstützen . Grundsätzlich sollte Ihr Code für Arrays mit einer Länge von bis zu 2 31 funktionieren, obwohl dies nicht unbedingt in Ihren Speicher passen oder innerhalb eines angemessenen Zeitraums vervollständigt werden muss. (Ich möchte einfach keine willkürlichen Größenbeschränkungen für Hardcode-Schleifen oder ähnliches sehen.)

Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes).

Bestenliste

Das folgende Snippet generiert eine Rangliste für alle Herausforderungen der Serie.

Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

(Die Sprache wird derzeit nicht angezeigt, das Snippet erfordert sie jedoch und analysiert sie. In Zukunft werde ich möglicherweise eine Bestenliste nach Sprachen hinzufügen.)

Martin Ender
quelle
7
Ich bin enttäuscht, dass wir nicht "schlau" sein und andere Bibliotheksfunktionen als "Zufallszahlen erhalten" verwenden dürfen . Wollen wir uns noch weitere 69 Implementierungen von Fisher-Yates-Shuffling ansehen? Bitte ziehen Sie in Betracht, diese Regel in zukünftigen Aufgaben zu entfernen. Warum auch eine zeitliche Beschränkung der Komplexität? Bitte denken Sie daran, es auf mindestens O (n ^ 2) zu entspannen. Ich denke auch, dass jemand eine besonders gelungene Implementierung finden könnte, wenn Sie O (n!) Zulassen.
Anatolyg
7
@anatolyg Das Aufheben der Beschränkungen bedeutet, dass jede Antwort entweder sortby(random)(der Grund für die zeitliche Beschränkung) oder einfach .shuffle()(der Grund für die eingebaute Beschränkung) lautet, was meiner Meinung nach weitaus weniger klug ist, als Fisher-Yates oder eine andere zu implementieren Ansatz.
Martin Ender
1
Wenn anstelle schlurfend, hat eine Funktion zur Rückkehr des Array, oder ist es genug , dass es geändert wird? Kann ich eine Funktion für shuffle(array)anstatt schreiben newArray=shuffle(array)?
Geobits
1
@Bakuriu Die Behauptung, dass Sie in linearer Zeit sortieren können, wenn die Zahlen festgelegt sind, entspricht der Behauptung, dass Sie in O (1) alles tun können, wenn die Eingabegrößen festgelegt sind. Die relevante Einschränkung sind auch Arrays mit fester Größe, nicht ganze Zahlen mit fester Größe - da die Arraygröße bestimmt, wie groß Ihre Zufallszahlen sein müssen. Wie auch immer, die Beschränkung der zeitlichen Komplexität gilt natürlich für den von Ihnen implementierten allgemeinen Algorithmus, wohingegen die Beschränkungen für die Eingabegrößen gelten, sodass Sie keine Ganzzahlen mit willkürlicher Genauigkeit verwenden müssen, wenn Ihre Sprache diese nicht standardmäßig verwendet .
Martin Ender
2
Warum wird Adáms Lösung als 43319 Bytes angezeigt, obwohl es tatsächlich 14 sind?
Boboquack

Antworten:

20

Dyalog APL, 25 24 Bytes

Zuerst für die 25-stellige Lösung: 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[⍵]

Nach einigen Äquivalenztransformationen auf dem oben genannten:

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

wir können die Aufgabe loswerden i←und einen Charakter speichern:

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

ngn
quelle
3
... Verstand. geblasen.
Danwyand
1
eine sprache die ich von rechts nach links lesen muss ?? Wow!
Luminous
5
@Luminous wie so oft in mathematischer Notation: sin cos ln sqrt x
ngn
4
@ngn wenn du es so ausdrückst, dass mein vorheriger Kommentar lächerlich aussieht. Ha.
Luminous
5
@ronalchn Es gibt 8-Bit-Codierungen für APL, wie diese oder diese andere; Ich habe gehört, Dyalog verwendet eine dieser Methoden als Alternative zu Unicode.
Anatolyg
12

80386 Maschinencode, 44 24 Bytes

Hexdump des Codes:

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

Vielen Dank an FUZxxl, der vorgeschlagen hat, die rdrandAnweisung zu verwenden.

Hier ist der Quellcode (kann von Visual Studio kompiliert werden):

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

Eine weitere Implementierung von Fisher-Yates. Der Großteil des Golfspiels wurde durch Übergabe von Parametern in Registern erzielt.

anatolyg
quelle
1
Sie könnten auch rdrandfür Scheiße und Kichern verwendet haben.
FUZxxl,
@FUZxxl Ich habe es total vergessen! Schade, dass es den interessantesten Teil über meine Antwort entfernt ...
Anatolyg
9

Java 88, 101

Ein einfaches Fisher-Yates-Shuffle erledigt den Trick. Ich habe das Gefühl, dass es hier ziemlich häufig verwendet wird, da es schnell und einfach zu implementieren ist. Hier drängen sich einige Loops / Aufgaben, aber es gibt ehrlich gesagt nicht zu viel zum Golfen. es ist von Natur aus nur kurz.

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

Mit einigen Zeilenumbrüchen:

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

Dadurch wird das ursprüngliche Array geändert s[]. Testprogramm:

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--;}
}
Geobits
quelle
1
Nein, die Herausforderung besagt, dass Sie davon ausgehen können, dass sie " über den angeforderten Bereich hinweg vollkommen gleichmäßig ist ". Der angeforderte Bereich von Math.random()hat eine Größe, die eine Potenz von zwei ist, sodass die Spezifikation nicht erfüllt wird.
Peter Taylor
1
Die Interpretationen von @PeterTaylor Jan und Geobits sind in der Tat so, wie ich es beabsichtigt habe - dass Sie sich keine Gedanken über die tatsächliche Zykluslänge Ihres PRNG machen müssen.
Martin Ender
1
@ Martinbüttner die taktlänge ist hier nicht das problem - das wird von deiner regel abgedeckt. Die Grobheit der Schwimmer ist.
John Dvorak
3
@TheBestOne Es ist ein Byte kürzer als die einzige aktuell veröffentlichte Python-Lösung;)
Geobits
1
Nicht mehr! : D
Sp3000
8

Python 2, 86 Bytes

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

Dies ist eine Funktion, die das Array an Ort und Stelle mischt, ohne es zurückzugeben, wobei eine einfache Implementierung des Fisher-Yates-Shuffle verwendet wird . Zufallszahlen von Python zu bekommen ist teuer ...

Vielen Dank an @xnor und @colevk für Tipps.

Sp3000
quelle
Dieser Bereichsausdruck sieht ziemlich umständlich aus. Sicherlich ist es kürzer, manuell als herunterzuzählen while i:i-=1;...?
Donnerstag,
@xnor Ja, das ist es - danke dafür. Ich vergesse immer wieder, dass dies whilein der Regel kürzer ist als forfür diese Art von Dingen ...
Sp3000
1
Awww ... jetzt schlägt meine Java-Antwort dies nicht. Ich war für eine kurze Zeit ziemlich glücklich :(
Geobits
Sie können weitere 2 Bytes speichern, i=len(L)indem Sie das Dekrement an den Anfang der while-Schleife setzen.
Colevk
8

J, 45 44 Zeichen

Das war eine knifflige Sache.

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

Hier ist eine Erklärung:

  1. # y: Die tally der y, dass die Anzahl der Elemente in ist y.
  2. ?@# y: Eine Zufallszahl, die gleichmäßig über den Bereich von 1bis verteilt ist(#y)-1 .
  3. x { y: Der Artikel aus dem y Index x.
  4. (<<<x) { y: Alle Artikel mit Ausnahme des Artikels bei Index xin y.
  5. x , y: y angehängt an x.
  6. x ({ , <^:3@[ { ]) y: Das Element bei Index xin y, dann alle anderen Elemente.
  7. (?@# ({ , <^:3@[ { ]) ]) yEin zufälliger davon y, dann alle anderen Gegenstände.
  8. x {. y: Die ersten xArtikel entnommen aus y.
  9. x }. y: Die ersten xGegenstände fielen aus y.
  10. x ({. , }.) y: Die ersten xElemente genommen aus y, dann werden die ersten xArtikel fiel ausy
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Die ersten xElemente genommen aus y, dann die ersten xElemente ausy wie in Ziffer 7 verarbeitet.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: Dasselbe mit dem Drop- In, um ein Zeichen zu speichern.
  13. u/ y: zwischen den Elementen von u eingefügty .
  14. < y: y boxed .
  15. <"0 y: Jeder Gegenstand in y Schachtel .
  16. i. y: ganze Zahlen von 0bis y - 1.
  17. i.@# y: ganze Zahlen von 0bis (#y) - 1.
  18. (<"0@i.@# , <) y: Ganzzahlen von 0bis zu (#y) - 1jeder Box und dann yin einer einzelnen Box. Dies ist erforderlich, da Arrays in J einheitlich sind. Eine Box verbirgt die Form ihres Inhalts.
  19. x u&v y: wie (v x) u (v y).
  20. > y: y geöffnet , das heißt, ohne seine Box.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y Die Phrase aus Nummer 12 galt für die Argumente ohne Box.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ ydie Phrase von Nr. 21 eingefügt zwischen Einzelteilen von y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) ydie Phrase von Nummer 22 wird auf das Ergebnis der Phrase von Nummer 18 angewendet, oder eine einheitliche Permutation der Gegenstände von y.
FUZxxl
quelle
1
Ich kann einfach nicht alle Klammern unterscheiden. Und das Triple-Boxen <@<@<@[ist auch ein Rätsel ... Warten auf Erklärung. :)
Randomra
2
Once this gets explained, I might be much more likely to upvote this answer ;-)
John Dvorak
@randomra Here you go.
FUZxxl
@JanDvorak Is the explanation satisfying?
FUZxxl
Great explanation! I didn't know about all the boxed use of from ({). And I really like the &>/ trick to manipulate a list. I'm sure I could have used it a couple times before.
randomra
5

Pyth, 25 bytes

Test it here.

Yet another Fisher-Yates implementation. Is essentially the same as @Sp3000 python solution, just in pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Thanks to @Jakube for the swapping trick

<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
quelle
You can save two bytes by combining those two list assignments: ` XXQN@QKKJ` instead of ` XQN@QK XQKJ`.
Jakube
@Jakube thanks for the tip. I knew there must have been a way to swap values in a list, and this is really smart. You should add it to the tips list.
Maltysen
4

Perl, 68 56 44

Like many other solutions, this uses the Fisher-Yates algorithm.

Using nutki's comment, 12 characters are saved by using $_ instead of $i and performing the operations in the array indices.

44:

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

56:

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

This is my first codegolf.

Bonsaigin
quelle
Not a bad start, I did not know that you can use @_[...] as rvalue like that. Can be golfed further into sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}.
nutki
3

C, 63 61 60 bytes

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

Just a straight implementation of Fischer-Yates that sorts the given array in place. Compiles and links perfectly fine with the visual studio compiler (vs2013, haven't tested the other versions) and the Intel Compiler. Nice looking function signature is s(int array[], int length). I'm legitimately impressed I beat Python and Ruby.

This does assume srand() is called and rand() is implemented properly, but I believe this rule allows for that:

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

Nicely formatted version:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
pseudonym117
quelle
I think it suffices to make the function header s(a,m)*a{, but I'm not sure and don't want to test either. You might want to do a xor-swap, like in a[i]^=a[m]^=a[i]^=a[m]. This also avoids the need to declare t.
FUZxxl
@FUZxxl I believe an xor swap causes problems if i==m.
Geobits
@Geobits indeed. I missed that possibility.
FUZxxl
I was just trying to figure out why that wasn't working... should have remembered that. Also I do need s(a,m)int*a for visual studio and the intel compiler. Don't have gcc or clang installed to test, but I assume they will also complain.
pseudonym117
This is pretty impressively golfed. After trying a lot of modifications that didn't save anything, I did manage to see a way to save 2 characters. If you change the swap order so that the first swap statement becomes t=a[i], you can then move the i=rand()%m-- statement inside as the array index.
Runer112
3

Octave, 88 77 bytes

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
quelle
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
quelle
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
quelle
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.
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
@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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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
quelle
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