Faro mischt ein Array

31

Ein Faro-Shuffle ist eine Technik, die häufig von Magiern verwendet wird, um ein Deck zu "mischen". Um einen Faro-Shuffle auszuführen, schneiden Sie zuerst das Deck in zwei gleiche Hälften und verschachteln dann die beiden Hälften. Beispielsweise

[1 2 3 4 5 6 7 8]

Faro wird gemischt

[1 5 2 6 3 7 4 8]

Dies kann beliebig oft wiederholt werden. Interessanterweise kehren Sie immer zum ursprünglichen Array zurück, wenn Sie dies genügend oft wiederholen. Beispielsweise:

[1 2 3 4 5 6 7 8]
[1 5 2 6 3 7 4 8]
[1 3 5 7 2 4 6 8]
[1 2 3 4 5 6 7 8]

Beachten Sie, dass 1 unten und 8 oben bleibt. Das macht dies zu einem äußeren Durcheinander . Dies ist eine wichtige Unterscheidung.

Die Herausforderung

Wenn ein Array von Ganzzahlen A und eine Zahl N gegeben sind , wird das Array nach N Faro-Shuffles ausgegeben . A kann wiederholte oder negative Elemente enthalten, hat jedoch immer eine gerade Anzahl von Elementen. Sie können davon ausgehen, dass das Array nicht leer ist. Sie können auch davon ausgehen, dass N eine nicht negative Ganzzahl ist, obwohl es 0 sein kann. Sie können diese Eingaben auf jede vernünftige Weise verwenden. Die kürzeste Antwort in Bytes gewinnt!

Test IO:

#N, A,                                              Output
1,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 5, 2, 6, 3, 7, 4, 8]
2,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 3, 5, 7, 2, 4, 6, 8]
7,  [-23, -37, 52, 0, -6, -7, -8, 89]               [-23, -6, -37, -7, 52, -8, 0, 89]
0,  [4, 8, 15, 16, 23, 42]                          [4, 8, 15, 16, 23, 42]
11, [10, 11, 8, 15, 13, 13, 19, 3, 7, 3, 15, 19]    [10, 19, 11, 3, 8, 7, 15, 3, 13, 15, 13, 19]

Und ein massiver Testfall:

23, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

Sollte ausgeben:

[1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100]  
DJMcMayhem
quelle
Kann das Array null Elemente enthalten?
Undichte Nonne
@LeakyNun Wir werden nein sagen, Sie müssen keine Null-Elemente behandeln.
DJMcMayhem
Related
Peter Taylor
1
Jede Permutation einer endlichen Menge wird, wenn sie genügend oft wiederholt wird, dort enden, wo sie begonnen hat. Das ist nichts Besonderes für Faro Shuffles.
Greg Martin

Antworten:

10

05AB1E , 5 Bytes

Code:

F2äø˜

Erklärung, Eingabe: N, array:

F      # Do the following N times
 2ä    # Split the array into 2 pieces
   ø   # Zip
    ˜  # Deep flatten

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
1
Verdammt, ich war zu langsam!
George Gibson
19

vim, 62 59 54

qrma50%mb:norm@q<cr>ggqOjdd'apjma'b@q<esc>0"qDJ<C-a>D@"i@r<esc>xxdd@"

Wow. Dies ist wahrscheinlich das hackigste, was ich für PPCG geschrieben habe, und das sagt etwas aus.

Die Eingabe wird in der ersten Zeile als N genommen, gefolgt von den Elementen des Arrays, wobei jedes in einer eigenen Zeile steht.

qr         first, we're going to record the contents of the @r macro. this is
             the macro which does the faro-shuffle operation.
  ma       set the mark 'a at the beginning of the file
  50%      move to the 50% point of the file (i.e. halfway down)
  mb       set another mark here
  :norm@q  evaluate the recursive macro @q. we'll get to what that does later,
             but the interesting part here is that it's :norm@q instead of @q.
             this is because a recursive macro terminates at the end of the
             file, which means when @q terminates, @r would also abort, which
             would make calling it with a count impossible. running @q under
             :norm prevents this.
  gg       move back to the top of the file for the next iteration
q          end recording
O          now we're inserting contents of the @q macro, the recursive part
             we can't record it directly because it's destructive
  j        move to line directly below mark 'b (which was just set before @q)
  dd       delete this line and bring it...
  'ap      up after mark 'a (which starts on line 1, bringing the N/2th line
             directly below line 1, aka line 2)
  jma      replace mark 'a one line below this so that the next time we call
             'ap, the line from the second half is interleaved with the lines
             from the first half
  'b       jump back to mark 'b (remember, 'b is the last line of the first
             half of the file, originally reached via 50%)
  @q       call ourselves, causing the macro to run until hitting EOF
0"qD       delete this into register "q
J          delete the empty line that remains
<C-a>      here's another interesting bit: we want to run @r N times. but 0@r
             means "go to column 0, and then run @r once." so we have to
             increment the input number...
D@"        and then *that* many times...
  i@r        insert @r...
xx         ... and finally, delete two characters, which is the extra @r from
             the increment
dd         delete the sequence of @rs into the "" register...
@"         and run it!

Ich habe beim Schreiben dieser Antwort möglicherweise mehrere VIM-Bugs gefunden:

  • Das Aufzeichnen von Makros ist nicht innerhalb anderer Makros (wenn der Text manuell festgelegt wird, nicht mit q) oder innerhalb von Makros möglich:*map s .

  • :let @a='<C-v><cr>'<cr>i<C-r>a gibt zwei Zeilenumbrüche aus, nicht einen, aus irgendeinem arkanen Grund.

Ich könnte diese später weiter untersuchen.

Danke an Dr. Green Eggs und Ham DJ für 3 Bytes!

Türknauf
quelle
4
Das ist schön und schrecklich. Ich habe wahrscheinlich nicht genug Geduld, um dies in vim zu tun. :PSie können auch 2 Bytes "rckvgg"rcdw@"i@r<esc>AA@R<C-v><esc><esc>0D@"
entfernen,
@DrGreenEggsandHamDJ Das erste kann ich nicht machen, weil das auch eine abschließende Zeile ergibt, aber die zweite Optimierung funktioniert. Vielen Dank!
Türklinke
7

Python 2, 59 Bytes

def f(n,L):exec"l=len(L)/2;L=(L+L[1:]*~-l)[::l];"*n;print L

Ein anderer Ansatz, etwas länger als die anderen Python-Antworten. Funktioniert nur für positive gerade Elementzahlen.

zB für 1, [1,2,3,4,5,6,7,8], nimm das Array und hänge len(L)/2-1Kopien von sich selbst minus dem ersten Element an, zB

[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]

Dann nimm jedes len(L)/2Element.

[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]
 ^       ^       ^       ^       ^       ^       ^       ^
Sp3000
quelle
6

Python, 68 57 Bytes

f=lambda n,x:n and f(n-1,sum(zip(x,x[len(x)/2:]),()))or x

Vielen Dank an @ Sp3000 für das Golfen mit 11 Bytes!

Teste es auf Ideone .

Dennis
quelle
6

Haskell, 62 Bytes

0!a=a
n!a|s<-length a=(n-1)![a!!mod(div(s*i+i)2)s|i<-[0..s-1]]

Sei s = 2 · t die Größe der Liste. Das i- te Element der neuen Liste wird erhalten, indem das Bildbeschreibung hier eingeben-te Element der alten Liste mit Nullindex und Modulo s genommen wird .

Beweis: wenn i = 2 · k gerade ist, dann

                                         Bildbeschreibung hier eingeben

und wenn i = 2 · k + 1 ungerade ist, dann

                        Bildbeschreibung hier eingeben

Die zur Indizierung verwendeten Werte sind also 0, t , 1, t + 1, 2, t + 2, ...

Lynn
quelle
5

J - 12 Bytes

Adverb (!) Nimmt links die Anzahl der Shuffles und rechts das zu mischende Array.

/:#/:@$0,#^:

Der J-Parser hat Regeln für das Schreiben stillschweigender Adverbien , aber sie haben eine sehr geringe Priorität: Wenn Sie eine Reihe von Verben als linkes Argument verwenden möchten, können Sie einen ansonsten erforderlichen Satz von Klammern weglassen. Das Obige ist also eigentlich eine Abkürzung für (/:#/:@$0,#)^:, bei der die Anzahl der Shuffles links als Adverb verwendet wird und die dann zu einer monadischen Funktion wird, bei der das Array rechts gemischt wird.

Das heißt, wir mischen wie folgt. #ist die Länge des Arrays, also 0,#eine Liste mit zwei Elementen: 0, gefolgt von etwas ungleich Null. Dann #/:@$repliziert , die in eine Liste , solange die Eingangsanordnung, und nimmt seine Sortiervektor .

Der Sortiervektor einer Liste ist die Information zum Sortieren der Liste: der (0-basierte) Index des kleinsten Elements, gefolgt vom Index des nächstkleineren usw. Zum Beispiel der Sortiervektor von0 1 0 1 ... also 0 2 4 ... 1 3 5 ....

Wenn J nun diesen Sortiervektor sortieren würde, würde er von Faro gemischt; aber das wäre trivial, da wir 0 1 2 3 ...zurückkommen würden. Also benutzen wir dyadic/: , um das Eingabearray so zu sortieren, als ob es wäre 0 2 4 ... 1 3 5 ... , was Faro es mischt.

Anwendungsbeispiel unten. Probieren Sie es selbst bei tryj.tk !

   1 (/:#/:@$0,#^:) 1 2 3 4 5 6 7 8
1 5 2 6 3 7 4 8

   f =: /:#/:@$0,#^:

   2  f  1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8

   7  f  _23 _37 52 0 _6 _7 _8 89   NB. "negative 1" is spelled _1
_23 _6 _37 _7 52 _8 0 89

   1  f  0 0 0 0 1 1 1              NB. odd-length lists
0 1 0 1 0 1 0
algorithmshark
quelle
5

Pyth - 8 7 Bytes

1 Byte dank @issacg gespeichert

usCc2GE

Probieren Sie es hier online aus .

Maltysen
quelle
2
Hmm ... es muss etwas falsch in der Jelly-Antwort sein, wenn Pyth Jelly schlägt.
Undichte Nonne
2
Tauschen Sie die Eingabereihenfolge aus und entfernen Sie die Q, um ein Byte zu speichern. Es muss etwas falsch mit der Pyth-Antwort sein, wenn Jelly Pyth schlägt. :)
Isaacg
@isaacg verdammt, hätte schwören können, dass ich das schon einmal versucht habe. Warum funktioniert das? sollte sich das nicht auf den default ubei none einhängen und festpunkt machen?
Maltysen
@Maltysen Du hast recht, ich glaube, es hat nur bei dem einen Testfall funktioniert, den ich ausprobiert habe. Das tut mir leid.
Isaacg
@LeakyNun Dank @Dennis und @issacg sind Pyth und Jelly jetzt gleich (7 Bytes). ; D
Kevin Cruijssen
3

Gelee, 9 7 Bytes

2 Bytes dank Dennis!

œs2ZFð¡

Probieren Sie es online!

Erläuterung

œs2ZFð¡  Main dyadic chain. Arguments: x,y
      ¡  Repeat the following y time:
œs2          Split into two.
   Z         Transpose.
    F        Flatten.

Vorherige 9-Byte-Version:

œs2ZF
Ç⁴¡

Probieren Sie es online!

Undichte Nonne
quelle
2

JavaScript (ES6), 61 51 Byte

(n,a)=>[...a].map((e,i)=>a[(i<<n)%~-a.length||i]=e)

Ändert das vorhandene Eingabearray und gibt eine Kopie des ursprünglichen Arrays zurück. Wenn dies nicht akzeptabel ist, &&akann ein Suffix angehängt werden, um das geänderte Array zurückzugeben. Funktioniert naufgrund der Einschränkungen der Ganzzahlarithmetik von JavaScript nur für kleine Werte von . 61 60-Byte-Rekursivversion, die mit einer größeren Version funktioniert n, basierend auf der @ Lynn-Formel:

f=(n,a,l=a.length)=>n?f(n-1,a.map((_,i)=>a[(i*-~l>>1)%l])):a
Neil
quelle
2

MATL , 11 Bytes

w:"tn2/e!1e

Danke an @Dennis für die Korrektur

Probieren Sie es online!

Erläuterung

w         % Take the two inputs N and A. Swap them
:         % Generate [1 2 ... N]
"         % Repeat N times
  tn2/    %   Duplicate A. Number of elements divided by 2
  e       %   Reshape to that number of rows
  !       %   Transpose
  1e      %   Reshape to one row
          % End (implicit)
          % Display (implicit)
Luis Mendo
quelle
Warum ist das wnotwendig?
David
@ David Das war die Korrektur. Ohne wird für N = 0 die Schleife nicht betreten und die zweite Eingabe wird nicht vorgenommen
Luis Mendo
Ahh das nervt!
David
2

J, 22, 19, 17 Bytes

3 Bytes dank @Gareth .

2 Bytes dank @algorithmshark .

-:@#({.,@,.}.)]^:

Verwendung

>> f =: -:@#({.,@,.}.)]^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

Wo >>ist STDIN und<<ist STDOUT.

Vorherige 22-Byte-Version:

({~[:,/@|:@i.2,-:@#)^:

Verwendung

>> f =: ({~[:,/@|:@i.2,-:@#)^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

Wo >>ist STDIN und <<ist STDOUT.

Undichte Nonne
quelle
Aufgrund der Parsing-Regeln von J können Sie die äußeren Parens für 2 Zeichen löschen.
Algorithmushai
Alternativ kann ein transponierter Index {~2,@|:@i.@,-:@#^:für 18 Bytes verwendet werden .
Meilen
Eine weitere Alternative , die verwendet 17 Bytes auch[:,@|:]]\~_2%~#^:
Meilen
@ MeilenIch glaube, ,@|:@$~2,-:@#^:funktioniert für 15 Bytes
Jonah
1

Mathematica 44 Bytes

Mit 4 Bytes dank @miles gespeichert.

Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&

Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]teilt die Liste in zwei gleiche Unterlisten auf und mischt Rifflesie.


 Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@8, 1]

{1, 5, 2, 6, 3, 7, 4, 8}


Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@100, 23]

{1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4 , 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36 , 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68 , 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100 }

DavidC
quelle
Mit TakeDropkönnen wir eine Lösung finden, die 40 Bytes verwendet und Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&gleichzeitig die ##zu analysierende Sequenz als zusätzliche Argumente verwendet Nest.
Meilen
@Meilen. Sehr nette Verwendung von TakeDrop. Und es ist besser, ##die Sequenz einzufügen.
DavidC
1

APL, 23 21 Zeichen

({⊃,/⍵(↑,¨↓)⍨2÷⍨⍴⍵}⍣N)A

Ohne die Annahme (Danke an Dennis) und 1 Zeichen kürzer:

({{∊,⌿2(2÷⍨≢⍵)⍴⍵}⍣⎕)⎕

Probieren Sie es online an .

user2070206
quelle
1

Java, 109 Bytes

int[]f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}return a;}

Erläuterung: Es gibt ein Muster dafür, wie sich die Elemente bewegen, wenn sie gemischt werden:

Sei x der ursprüngliche Index

sei y der neue Index

L sei die Länge des Arrays

  • y ist doppelt x
  • Wenn x größer oder gleich der Hälfte von L ist, erhöhen Sie y
  • Halten Sie y innerhalb der Grenzen des Arrays

oder als Code: y=(2*x+x/(L/2))%L

Dies setzt voraus, dass die Zeichen bei 0 beginnen. Hier ist der Code, der weiter erklärt wird:

int[] faroShuffle( int[] array, int numberOfShuffles ) {
    //repeat the faro shuffle n times
    for( int index, length=array.length, destination[]; 0<numberOfShuffles--; array=destination ) {
        //new array to copy over the elements
        destination=new int[length];
        //copy the elements into the new array
        for( index=0; index<length; index++ )
            destination[(2*index+2*index/length)%length]=array[index];
        //at the end of each loop, copy the reference to the new array and use it going forward
    }
    return array;
}  

siehe ideone für testfälle

Jack Ammo
quelle
Ich weiß, es ist mehr als ein Jahr her, aber Sie können ein paar Teile Golf spielen: void f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d)for(d=new int[q],x=0;x<q;)d[(2*x+2*x/q)%q]=a[x++];}( 107 Bytes - Ihre aktuelle Antwort ist 119 BTW, nicht 109, also -12 Bytes). Da Sie das Eingabearray ändern, müssen Sie es nicht zurückgeben. Sie können es daher in einen leeren Wert ändern, um die Anzahl der Bytes zu verringern. Oh, und wenn Sie mit Curry auf ein Java 8 Lambda konvertieren, können Sie es noch kürzer machen:a->n->{for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}} ( 96 Bytes )
Kevin Cruijssen
1

Julia, 45 42 Bytes

a\n=n>0?reshape(a,endof(a)÷2,2)'[:]\~-n:a

Probieren Sie es online!

Wie es funktioniert

Wir definieren den binären Operator \für diese Aufgabe (neu) . Sei a ein Array und n eine nicht negative ganze Zahl.

Wenn n positiv ist, mischen wir das Array. Dies wird erreicht, indem es in eine Matrix der Länge (a) ÷ 2 Zeilen und zwei Spalten umgeformt wird. 'transponiert die resultierende Matrix, erstellt zwei Zeilen und reduziert das Ergebnis mit [:]. Da Julia Matrizen in Spalten-Hauptreihenfolge speichert, verschachtelt dies die beiden Zeilen.

Danach rufen wir \rekursiv mit den gemischten Buchstaben a und n - 1 ( ~-n) als Argumente auf und führen so zusätzliche Mischvorgänge durch. Sobald n 0 erreicht , geben wir den aktuellen Wert von zurück a zurück .

Dennis
quelle
0

Pyke, 7 Bytes

VDlec,s

Probieren Sie es hier aus!

V       - Repeat N times:
 D      -  a,b = a (2nd arg first time round)
  le    -  b = len(b)//2
    c   -  a = chunk(a,b)
     ,  -  a = zip(*a)
      s -  a = sum(a, [])
Blau
quelle
0

Eigentlich 15 Bytes

`;l½≈@│t)HZ♂i`n

Probieren Sie es online!

Erläuterung:

`;l½≈@│t)HZ♂i`n
`            `n  do the following n times:
 ;l½≈              push half the length of the array
     @             swap
      │            duplicate entire stack
       t)H         last L//2 elements, first L//2 elements
          Z♂i      zip, flatten each element
Mego
quelle
0

Prolog, 116 Bytes

a([],[[],[]]).
a([H,I|T],[[H|U],[I|V]]):-a(T,[U,V]).
f(X,0,X).
f(X,N,Y):-N>0,M is N-1,f(X,M,Z),a(Z,[A,B]),append(A,B,Y).

Verwendung

?- f([1,2,3,4,5,6,7,8],2,X).
X = [1, 5, 2, 6, 3, 7, 4, 8] ;
false.
Undichte Nonne
quelle
0

PHP, 98 Bytes

function($a,$n){while($n--)for($z=count($a)/2;$z;)array_splice($a,$z--,0,array_pop($a));return$a;}

Probieren Sie es online aus .

Titus
quelle