Faro przetasowuje tablicę


31

Faro Shuffle to technika często używana przez magów do „Shuffle” talię. Aby wykonać losowanie Faro, najpierw pociąć talię na 2 równe połowy, a następnie przełożyć dwie połowy. Na przykład

[1 2 3 4 5 6 7 8]

Faro jest potasowany

[1 5 2 6 3 7 4 8]

Można to powtórzyć dowolną liczbę razy. Co ciekawe, jeśli powtórzysz tyle razy, zawsze znajdziesz się w oryginalnej tablicy. Na przykład:

[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]

Zauważ, że 1 pozostaje na dole, a 8 na górze. To sprawia, że ​​jest to tasowanie zewnętrzne . To ważne rozróżnienie.

Wyzwanie

Biorąc pod uwagę tablicę liczb całkowitych A i liczbę N , wypisz tablicę po tasowaniu N Faro. A może zawierać powtarzające się lub ujemne elementy, ale zawsze będzie miała parzystą liczbę elementów. Możesz założyć, że tablica nie będzie pusta. Możesz również założyć, że N będzie nieujemną liczbą całkowitą, chociaż może wynosić 0. Możesz wprowadzić te dane wejściowe w dowolny rozsądny sposób. Najkrótsza odpowiedź w bajtach wygrywa!

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]

I ogromny przypadek testowy:

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]

Powinien generować:

[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]  

Czy tablica może zawierać zero elementów?
Leaky Nun

@LeakyNun Powiemy nie, nie musisz obsługiwać elementów zerowych.
DJMcMayhem



1
Każda permutacja zbioru skończonego, jeśli powtórzona wystarczająco wiele razy, zakończy się tam, gdzie się rozpoczęła; nie jest to wyjątkowe w przypadku losowania Faro.
Greg Martin

Odpowiedzi:


10

05AB1E , 5 bajtów

Kod:

F2äø˜

Objaśnienie, dane wejściowe: N, array:

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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .


1
Cholera, byłem zbyt wolny!
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@"

Łał. Jest to prawdopodobnie najbardziej hacka rzecz, którą napisałem dla PPCG, i to coś mówi.

Dane wejściowe są przyjmowane jako N w pierwszym wierszu, po których następują elementy tablicy, każdy w osobnym wierszu.

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!

Prawdopodobnie znalazłem kilka błędów vima podczas pisania tej odpowiedzi:

  • nagrywanie makr nie jest możliwe w obrębie innych makr (przy ręcznym ustawianiu tekstu, nie za pomocą q) lub w obrębie :*maps.

  • :let @a='<C-v><cr>'<cr>i<C-r>a wypisuje dwie nowe linie, a nie jedną z jakiegokolwiek tajemniczego powodu.

Mogę to zbadać później.

Dzięki Dr Green Eggs i Ham DJ za 3 bajty!


4
To jest piękne i przerażające. Prawdopodobnie nie mam dość cierpliwości, aby to zrobić w vimie. :PMożesz także zdjąć 2 bajty, wykonując "rckzamiast vgg"rc, i możesz zdjąć kolejne 5, wykonując dw@"i@r<esc>zamiastAA@R<C-v><esc><esc>0D@"
DJMcMayhem

@DrGreenEggsandHamDJ Nie mogę zrobić tego pierwszego, ponieważ pobiera on również końcowy znak nowej linii, ale ta druga optymalizacja działa. Dzięki!
Klamka

7

Python 2, 59 bajtów

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

Inne podejście, nieco dłuższe niż inne odpowiedzi w języku Python. Działa tylko w przypadku dodatniej parzystej liczby elementów.

np. 1, [1,2,3,4,5,6,7,8]weź tablicę i dołącz jej len(L)/2-1kopie minus pierwszy element, np

[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]

Następnie weź każdy 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]
 ^       ^       ^       ^       ^       ^       ^       ^

6

Python, 68 57 bajtów

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

Dzięki @ Sp3000 za grę w golfa z 11 bajtów!

Przetestuj na Ideone .


6

Haskell, 62 bajty

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

Niech s = 2 · t będzie wielkością listy. I -ty element nowej listy uzyskuje się poprzez poświęcenie enter image description here-ty element starej listy, zero-indeksowane, modulo s .

Dowód: jeśli i = 2 · k jest parzyste, to

                                         enter image description here

a jeśli i = 2 · k + 1 jest nieparzyste, to

                        enter image description here

Zatem wartości stosowane do indeksowania to 0, t , 1, t + 1, 2, t + 2,…


5

J - 12 bajtów

Przysłówek (!) Przyjmujący liczbę przetasowań po lewej stronie i tablicę do przetasowania po prawej stronie.

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

Parser J ma zasady pisania przysłówków cichych , ale mają one bardzo niski priorytet: jeśli chcesz użyć ciągu czasowników jako lewego argumentu, możesz pominąć niezbędny zestaw nawiasów. Tak więc powyższe jest w rzeczywistości skrótem (/:#/:@$0,#)^:, który przyjmuje liczbę przetasowań po lewej stronie jako przysłówek, a następnie staje się funkcją monadyczną, która przetasowuje tablicę po prawej stronie.

To powiedziawszy, tasujemy w następujący sposób. #jest długością tablicy, więc 0,#jest listą dwóch elementów: 0, po której następuje coś niezerowego. Następnie #/:@$powiela to na listę tak długo, jak tablica wejściowa i pobiera wektor sortowania .

Wektor sortowania listy jest informacją o sposobie sortowania listy: invdex (oparty na 0) najmniejszego elementu, po którym następuje indeks następnej najmniejszej itd. Na przykład wektor sortowania 0 1 0 1 ...będzie więc0 2 4 ... 1 3 5 ....

Gdyby J miał teraz posortować ten wektor sortowania, Faro go przetasował; ale byłoby to trywialne, ponieważ wrócilibyśmy 0 1 2 3 .... Dlatego używamy narzędzia Diadic/: do sortowania tablicy wejściowej tak, jakby była 0 2 4 ... 1 3 5 ..., which Faro-shuffles it.

Przykładowe użycie poniżej. Wypróbuj sam na 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

5

Pyth - 8 7 bytes

saved 1 byte thanks to @issacg

usCc2GE

Try it online here.


2
Hmm... there must be something wrong in the Jelly answer if Pyth beats Jelly.
Leaky Nun

2
Swap the input order and remove the Q to save a byte. There must be something wrong with the Pyth answer if Jelly beats Pyth. :)
isaacg

@isaacg darn, could've sworn i'd tried that before. Why does that work? shouldn't that hook onto the default for u with None and do fixed point?
Maltysen

@Maltysen You're right, I think it only happened to work on the one test case I tried. Sorry about that.
isaacg

@LeakyNun Thanks to @Dennis and @issacg, Pyth and Jelly are now equal (7 bytes). ;D
Kevin Cruijssen

3

Jelly, 9 7 bytes

2 bytes thanks to Dennis!

œs2ZFð¡

Try it online!

Explanation

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

Previous 9-byte version:

œs2ZF
Ç⁴¡

Try it online!


2

JavaScript (ES6), 61 51 bytes

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

Modifies the input array in place and returns a copy of the original array. If this is unacceptable, &&a can be suffixed to return the modified array. Only works for small values of n due to the limitations of JavaScript's integer arithmetic. 61 60 byte recursive version that works with larger n, based on @Lynn's formula:

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

2

MATL, 11 bytes

w:"tn2/e!1e

Thanks to @Dennis for a correction

Try it online!

Explanation

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)

Why is the w necessary?
David

@David That was the correction. Without it, for N = 0 the loop is not entered and the second input is not taken
Luis Mendo

Ahh that's annoying!
David

2

J, 22 19 17 bytes

3 bytes thanks to @Gareth.

2 bytes thanks to @algorithmshark.

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

Usage

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

Where >> is STDIN and << is STDOUT.

Previous 22-byte version:

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

Usage

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

Where >> is STDIN and << is STDOUT.


Because of J's parsing rules, you can drop the outer parens for 2 chars.
algorithmshark

Alternative using a transposed index {~2,@|:@i.@,-:@#^: for 18 bytes.
miles

Another alternative that uses 17 bytes also [:,@|:]]\~_2%~#^:
miles

@milesI believe ,@|:@$~2,-:@#^: works for 15 bytes
Jonah

1

Mathematica 44 bytes

With 4 bytes saved thanks to @miles.

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

Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles] splits the list into two equal sublists and shuffles (Riffles) them.


 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}


Using TakeDrop we can find a solution using 40 bytes as Riffle@@TakeDrop[#,Length@#/2]&~Nest~##& while also taking the sequence ## to be parsed as additional arguments to Nest.
miles

@miles. Very nice use of TakeDrop. And it is better to use ## to insert the sequence.
DavidC

1

APL, 23 21 chars

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

Without the assumption (Thanks to Dennis) and 1 char shorter:

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

Try it on online.


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

Explanation: There is a pattern to how the elements move when they are faro shuffled:

let x be the original index

let y be the new index

let L be the length of the array

  • y is double x
  • if x is greater than or equal to half of L then increment y
  • keep y within the array's bounds

or as code: y=(2*x+x/(L/2))%L

This assumes that indicies start at 0. Here's the code further explained:

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

see ideone for test cases


I know it's been more than a year, but you can golf a few parts: 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 - your current answer is 119 btw, not 109, so -12 bytes). Since you modify the input array, there is no need to return it, so you can change it to a void to reduce bytes. Oh, and if you convert to a Java 8 lambda with currying you could make it even shorter: 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

Try it online!

How it works

We (re)define the binary operator \ for this task. Let a be an array and n a non-negative integer.

If n is positive, we shuffle the array. This is achieved by reshaping it into a matrix of length(a) ÷ 2 rows and two columns. ' transposes the resulting matrix, creating of two rows, then flattening the result with [:]. Since Julia stores matrices in column-major order, this interleaves the two rows.

Afterwards, we call \ recursively with the shuffled a and n - 1 (~-n) as arguments, thus performing additional shuffles. Once n reaches 0, we return the current value of a.


0

Pyke, 7 bytes

VDlec,s

Try it here!

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, [])

0

Actually, 15 bytes

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

Try it online!

Explanation:

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

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

Usage

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


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

Try it online.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.