Faro baraja una matriz

31

Un faro aleatorio es una técnica utilizada frecuentemente por los magos para "barajar" un mazo. Para realizar un barajado de Faro, primero cortas la baraja en 2 mitades iguales y luego intercalas las dos mitades. Por ejemplo

[1 2 3 4 5 6 7 8]

Faro barajado es

[1 5 2 6 3 7 4 8]

Esto se puede repetir cualquier cantidad de veces. Curiosamente, si repite esto suficientes veces, siempre terminará en la matriz original. Por ejemplo:

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

Observe que 1 permanece en la parte inferior y 8 permanece en la parte superior. Eso hace que esto sea una confusión exterior . Esta es una distinción importante.

El reto

Dada una matriz de enteros A , y un número N , genera la matriz después de que N Faro baraje. A puede contener elementos repetidos o negativos, pero siempre tendrá un número par de elementos. Puede suponer que la matriz no estará vacía. También puede suponer que N será un número entero no negativo, aunque puede ser 0. Puede tomar estas entradas de cualquier manera razonable. ¡La respuesta más corta en bytes gana!

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

Y, un caso de prueba masivo:

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]

Debería dar salida:

[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
fuente
¿Puede la matriz contener cero elementos?
Leaky Nun
@LeakyNun Diremos que no, no tiene que manejar cero elementos.
DJMcMayhem
Relacionado
Peter Taylor
1
Cualquier permutación de un conjunto finito, si se repite suficientes veces, terminará donde comenzó; Esto no es especial para barajar Faro.
Greg Martin

Respuestas:

10

05AB1E , 5 bytes

Código:

F2äø˜

Explicación, entrada: N, array:

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

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
1
¡Maldición, fui demasiado lento!
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@"

Guau. Esta es posiblemente la cosa más pirata que he escrito para PPCG, y eso dice algo.

La entrada se toma como N en la primera línea seguida de los elementos de la matriz, cada uno en su propia línea.

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!

En realidad, posiblemente encontré varios errores vim al escribir esta respuesta:

  • no es posible grabar macros dentro de otras macros (al configurar su texto manualmente, no con q) o dentro de :*maps.

  • :let @a='<C-v><cr>'<cr>i<C-r>a genera dos nuevas líneas, no una, por cualquier razón arcana.

Podría investigar eso más adelante.

¡Gracias al Dr. Green Eggs y Ham DJ por 3 bytes!

Pomo de la puerta
fuente
44
Esto es hermoso y horrible. Probablemente no tengo suficiente paciencia para hacer esto en vim. :PAdemás, puede quitar 2 bytes haciendo en "rcklugar de vgg"rc, y puede quitar otros 5 haciendo en dw@"i@r<esc>lugar deAA@R<C-v><esc><esc>0D@"
DJMcMayhem
@DrGreenEggsandHamDJ No puedo hacer eso primero porque también toma una nueva línea final, pero esa segunda optimización funciona. ¡Gracias!
Pomo de la puerta
7

Python 2, 59 bytes

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

Un enfoque diferente, un poco más largo que las otras respuestas de Python. Solo funciona para números pares positivos de elementos.

por ejemplo 1, [1,2,3,4,5,6,7,8], para tomar la matriz y agregar len(L)/2-1copias de sí mismo menos el primer elemento, por ejemplo

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

Luego toma cada len(L)/2elemento.

[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
fuente
6

Python, 68 57 bytes

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

¡Gracias a @ Sp3000 por jugar 11 bytes!

Pruébalo en Ideone .

Dennis
fuente
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]]

Sea s = 2 · t el tamaño de la lista. El i -ésimo elemento de la nueva lista se obtiene tomando el ingrese la descripción de la imagen aquí-ésimo elemento de la lista anterior, indexado a cero, módulo s .

Prueba: si i = 2 · k es par, entonces

                                         ingrese la descripción de la imagen aquí

y si i = 2 · k + 1 es impar, entonces

                        ingrese la descripción de la imagen aquí

Por lo tanto, los valores utilizados para la indexación son 0, t , 1, t + 1, 2, t + 2, ...

Lynn
fuente
5

J - 12 bytes

Adverbio (!) Toma el número de barajaduras a la izquierda y la matriz para barajar a la derecha.

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

El analizador J tiene reglas para escribir adverbios tácitos , pero tienen una precedencia muy baja: si desea utilizar un tren de verbos como argumento izquierdo, puede omitir un conjunto de paréntesis que de otro modo sería necesario. Entonces, lo anterior es realmente la abreviatura de (/:#/:@$0,#)^:, que toma el número de barajaduras a la izquierda como un adverbio, y luego se convierte en una función monádica que lleva la matriz a barajar a la derecha.

Dicho esto, barajamos de la siguiente manera. #es la longitud de la matriz, por lo que 0,#es una lista de dos elementos: 0 seguido de algo distinto de cero. Luego #/:@$replica eso en una lista siempre que la matriz de entrada, y toma su vector de clasificación .

El vector de clasificación de una lista es la información sobre cómo ordenar la lista: el invdex (basado en 0) del elemento más pequeño, seguido del índice del siguiente más pequeño, y así sucesivamente. Por ejemplo, el vector de clasificación de 0 1 0 1 ...será así 0 2 4 ... 1 3 5 ....

Si J ahora ordenara este vector de clasificación, Faro lo barajaría; pero eso sería trivial, ya que volveríamos 0 1 2 3 .... Entonces usamos dyadic/: para ordenar la matriz de entrada como si fuera 0 2 4 ... 1 3 5 ... , lo que Faro la baraja.

Ejemplo de uso a continuación. Pruébelo usted mismo en 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
Algoritmo de tiburón
fuente
5

Pyth - 8 7 bytes

guardado 1 byte gracias a @issacg

usCc2GE

Pruébelo en línea aquí .

Maltysen
fuente
2
Hmm ... debe haber algo mal en la respuesta de Jelly si Pyth vence a Jelly.
Leaky Nun
2
Cambie el orden de entrada y elimine Qpara guardar un byte. Debe haber algo mal con la respuesta de Pyth si Jelly vence a Pyth. :)
isaacg
@isaacg maldita sea, podría haber jurado que lo había intentado antes. ¿Por qué funciona eso? ¿no debería engancharse al valor predeterminado para ucon None y hacer punto fijo?
Maltysen
@Maltysen Tienes razón, creo que solo funcionó en el único caso de prueba que probé. Lo siento por eso.
isaacg
@LeakyNun Gracias a @Dennis y @issacg , Pyth y Jelly ahora son iguales (7 bytes). ; D
Kevin Cruijssen
3

Jalea, 9 7 bytes

2 bytes gracias a Dennis!

œs2ZFð¡

Pruébalo en línea!

Explicación

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

Versión anterior de 9 bytes:

œs2ZF
Ç⁴¡

Pruébalo en línea!

Monja permeable
fuente
2

JavaScript (ES6), 61 51 bytes

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

Modifica la matriz de entrada en su lugar y devuelve una copia de la matriz original. Si esto es inaceptable, &&apuede tener el sufijo para devolver la matriz modificada. Solo funciona para valores pequeños ndebido a las limitaciones de la aritmética de enteros de JavaScript. 61 Versión recursiva de 60 bytes que funciona con versiones más grandes n, basada en la fórmula de @ Lynn:

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

MATL , 11 bytes

w:"tn2/e!1e

Gracias a @Dennis por una corrección

Pruébalo en línea!

Explicación

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
fuente
¿Por qué es wnecesario?
David
@David Esa fue la corrección. Sin él, para N = 0 no se ingresa el bucle y no se toma la segunda entrada
Luis Mendo
Ahh eso es molesto!
David
2

J, 22 19 17 bytes

3 bytes gracias a @Gareth .

2 bytes gracias a @algorithmshark .

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

Uso

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

Donde >>es STDIN y <<es STDOUT.

Versión anterior de 22 bytes:

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

Uso

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

Donde >>es STDIN y <<es STDOUT.

Monja permeable
fuente
Debido a las reglas de análisis de J , puedes soltar los parens externos por 2 caracteres.
algorithmshark
Alternativa usando un índice transpuesto {~2,@|:@i.@,-:@#^:para 18 bytes .
millas
Otra alternativa que utiliza 17 bytes también[:,@|:]]\~_2%~#^:
millas
@miles Creo que ,@|:@$~2,-:@#^:funciona para 15 bytes
Jonás
1

Mathematica 44 bytes

Con 4 bytes guardados gracias a @miles.

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

Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]divide la lista en dos sublistas iguales y las baraja Riffle.


 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
fuente
Usando TakeDroppodemos encontrar una solución usando 40 bytes , Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&mientras tomamos la secuencia ##para analizar como argumentos adicionales Nest.
millas
@miles. Muy buen uso de TakeDrop. Y es mejor usar ##para insertar la secuencia.
DavidC
1

APL 23 21 caracteres

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

Sin la suposición (gracias a Dennis) y 1 char más corto:

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

Pruébalo en línea .

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

Explicación: Hay un patrón de cómo se mueven los elementos cuando se barajan de forma aleatoria:

sea ​​x el índice original

deja ser el nuevo índice

deja que L sea la longitud de la matriz

  • y es doble x
  • si x es mayor o igual que la mitad de L, entonces incremente y
  • mantener y dentro de los límites de la matriz

o como código: y=(2*x+x/(L/2))%L

Esto supone que las indicaciones comienzan en 0. Aquí está el código más explicado:

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

ver ideone para casos de prueba

Jack munición
fuente
Sé que ha pasado más de un año, pero puedes jugar al golf algunas partes: 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 - tu respuesta actual es 119 por cierto, no 109, entonces -12 bytes). Como modifica la matriz de entrada, no hay necesidad de devolverla, por lo que puede cambiarla a un vacío para reducir bytes. Ah, y si te conviertes en un Java 8 lambda con curry, podrías hacerlo aún más corto: 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

Pruébalo en línea!

Cómo funciona

Nosotros (re) definimos el operador binario \para esta tarea. Deje a ser una matriz yn un número entero no negativo.

Si n es positivo, barajamos la matriz. Esto se logra al darle forma a una matriz de longitud (a) ÷ 2 filas y dos columnas. 'transpone la matriz resultante, crea dos filas y luego aplana el resultado con [:]. Como Julia almacena las matrices en el orden de columnas principales, esto intercala las dos filas.

Posteriormente, invocamos \recursivamente con el aleatorio a y n - 1 ( ~-n) como argumentos, realizando así barajamientos adicionales. Una vez que n alcanza 0 , devolvemos el valor actual de a .

Dennis
fuente
0

Pyke, 7 bytes

VDlec,s

Pruébalo aquí!

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

En realidad, 15 bytes

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

Pruébalo en línea!

Explicación:

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

Prólogo, 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).

Uso

?- f([1,2,3,4,5,6,7,8],2,X).
X = [1, 5, 2, 6, 3, 7, 4, 8] ;
false.
Monja permeable
fuente
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;}

Pruébalo en línea .

Tito
fuente