Faro embaralha uma matriz

31

Um shuffle de Faro é uma técnica frequentemente usada por mágicos para "embaralhar" um baralho. Para executar um embaralhamento de Faro, você primeiro corta o baralho em 2 partes iguais e depois intercala as duas partes. Por exemplo

[1 2 3 4 5 6 7 8]

Faro embaralhado é

[1 5 2 6 3 7 4 8]

Isso pode ser repetido inúmeras vezes. Curiosamente, se você repetir isso várias vezes, sempre retornará à matriz original. Por exemplo:

[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 na parte inferior e 8 permanece na parte superior. Isso faz disso um shuffle externo . Esta é uma distinção importante.

O desafio

Dada uma matriz de números inteiros A e um número N , produza a matriz após N Faro embaralhar. A pode conter elementos repetidos ou negativos, mas sempre terá um número par de elementos. Você pode assumir que a matriz não estará vazia. Você também pode assumir que N será um número inteiro não negativo, embora possa ser 0. Você pode receber essas entradas de qualquer maneira razoável. A resposta mais curta em bytes vence!

Teste de E / S:

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

E, um enorme caso de teste:

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]

Saída deve:

[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
fonte
A matriz pode conter zero elementos?
Freira vazada
@LeakyNun Vamos dizer que não, você não precisa lidar com zero elementos.
DJMcMayhem
Relacionado
Peter Taylor
1
Qualquer permutação de um conjunto finito, se repetida várias vezes, terminará no local onde começou; isso não é especial para os embarques de Faro.
Greg Martin

Respostas:

10

05AB1E , 5 bytes

Código:

F2äø˜

Explicação, entrada: N, array:

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

Usa a codificação CP-1252 . Experimente online! .

Adnan
fonte
1
Porra, eu estava muito 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@"

Uau. Essa é possivelmente a coisa mais hacker que eu escrevi para o PPCG, e isso está dizendo algo.

A entrada é tomada como N na primeira linha seguida pelos elementos da matriz, cada um em sua própria linha.

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!

Na verdade, eu encontrei vários erros do vim ao escrever esta resposta:

  • não é possível gravar macros em outras macros (ao definir o texto manualmente, não com q) ou dentro de :*maps.

  • :let @a='<C-v><cr>'<cr>i<C-r>a gera duas novas linhas, não uma, por qualquer motivo misterioso.

Eu poderia investigar isso mais tarde.

Obrigado ao Dr. Green Eggs e Ham DJ por 3 bytes!

Maçaneta da porta
fonte
4
Isso é lindo e horripilante. Provavelmente não tenho paciência suficiente para fazer isso no vim. :PAlém disso, você pode tirar 2 bytes fazendo em "rckvez de vgg"rce você pode tirar outros 5 fazendo em dw@"i@r<esc>vez deAA@R<C-v><esc><esc>0D@"
DJMcMayhem
@DrGreenEggsandHamDJ Não é possível fazer o primeiro porque ele também pega uma nova linha à direita, mas essa segunda otimização funciona. Obrigado!
Maçaneta
7

Python 2, 59 bytes

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

Uma abordagem diferente, um pouco mais longa que as outras respostas do Python. Funciona apenas para números pares positivos de elementos.

por exemplo 1, [1,2,3,4,5,6,7,8], para , pegue a matriz e acrescente len(L)/2-1cópias de si menos o primeiro elemento, por exemplo

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

Então pegue todo len(L)/2elemento th.

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

Python, 68 57 bytes

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

Graças ao @ Sp3000 por jogar fora 11 bytes!

Teste em Ideone .

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

Seja s = 2 · t o tamanho da lista. O i- ésimo elemento da nova lista é obtido usando o insira a descrição da imagem aqui-ésimo elemento da lista antiga, indexada a zero, módulos s .

Prova: se i = 2 · k é par, então

                                         insira a descrição da imagem aqui

e se i = 2 · k + 1 é ímpar, então

                        insira a descrição da imagem aqui

Assim, os valores usados ​​para indexação são 0, t , 1, t + 1, 2, t + 2,…

Lynn
fonte
5

J - 12 bytes

Advérbio (!) Tendo o número de shuffles à esquerda e a matriz para shuffle à direita.

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

O analisador J possui regras para escrever advérbios tácitos , mas eles têm uma precedência muito baixa: se você quiser usar um conjunto de verbos como argumento à esquerda, poderá omitir um conjunto de parênteses caso contrário necessário. Portanto, o texto acima é realmente abreviado (/:#/:@$0,#)^:, o que leva o número de shuffles à esquerda como advérbio e, em seguida, torna-se uma função monádica, levando a matriz a shuffle à direita.

Dito isto, nós embaralhamos da seguinte maneira. #é o comprimento da matriz, assim 0,#como uma lista de dois elementos: 0 seguida por algo diferente de zero. Em seguida, #/:@$replica isso em uma lista enquanto a matriz de entrada e pega seu vetor de classificação .

O vetor de classificação de uma lista é a informação de como classificar a lista: o invdex (com base em 0) do menor elemento, seguido pelo índice do próximo menor e assim por diante. Por exemplo, o vetor de classificação de 0 1 0 1 ...será assim 0 2 4 ... 1 3 5 ....

Se J agora classificasse esse vetor de classificação, Faro o embaralharia; mas isso seria trivial, já que voltaríamos 0 1 2 3 .... Portanto, usamos diádico/: para classificar a matriz de entrada como se fosse 0 2 4 ... 1 3 5 ... , o que Faro a embaralha.

Exemplo de uso abaixo. Experimente você mesmo em 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
algoritmshark
fonte
5

Pitão - 8 7 bytes

economizou 1 byte graças a @issacg

usCc2GE

Experimente online aqui .

Maltysen
fonte
2
Hmm ... deve haver algo errado na resposta da geléia se Pyth vencer a geléia.
Freira vazada
2
Troque a ordem de entrada e remova-a Qpara salvar um byte. Deve haver algo errado com a resposta Pyth se Jelly vencer Pyth. :)
isaacg
@isaacg danado, poderia ter jurado que eu tentei isso antes. Por que isso funciona? esse gancho não deveria ser o padrão para uNone e não o ponto fixo?
Maltysen 06/06/19
@ Maltysen Você está certo, acho que só funcionou no caso de teste que eu tentei. Me desculpe por isso.
Isaacg
Graças a @LeakyNun @ Dennis e @issacg , Pyth e geléia são agora iguais (7 bytes). ; D
Kevin Cruijssen
3

Geléia, 9 7 bytes

2 bytes graças a Dennis!

œs2ZFð¡

Experimente online!

Explicação

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

Versão anterior de 9 bytes:

œs2ZF
Ç⁴¡

Experimente online!

Freira Furada
fonte
2

JavaScript (ES6), 61 51 bytes

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

Modifica a matriz de entrada no local e retorna uma cópia da matriz original. Se isso for inaceitável, &&apode ser um sufixo para retornar a matriz modificada. Funciona apenas para valores pequenos ndevido às limitações da aritmética inteira do JavaScript. 61 60 byte versão recursiva que funciona com o maior n, com base em @ fórmula de Lynn:

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

MATL , 11 bytes

w:"tn2/e!1e

Obrigado a @Dennis por uma correção

Experimente online!

Explicação

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
fonte
Por que é wnecessário?
David David
@ David Essa foi a correção. Sem ele, para N = 0 a malha não está inscrita e a segunda entrada não é tomado
Luis Mendo
Ahh isso é chato!
David
2

J, 22 19 17 bytes

3 bytes graças a @Gareth .

2 bytes graças a @algorithmshark .

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

Uso

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

Onde >>está STDIN e <<está STDOUT.

Versão 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

Onde >>está STDIN e <<está STDOUT.

Freira Furada
fonte
Por causa das regras de análise de J , você pode eliminar as parênteses externas por 2 caracteres.
algorithmshark
Alternativa usando um índice transposto {~2,@|:@i.@,-:@#^:para 18 bytes .
milhas
Outra alternativa que usa 17 bytes também[:,@|:]]\~_2%~#^:
miles
@milesI acredito que ,@|:@$~2,-:@#^:funciona para 15 bytes
Jonah
1

Mathematica 44 bytes

Com 4 bytes salvos, graças ao @miles.

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

Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]divide a lista em duas sublistas iguais e as embaralha 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
fonte
Usando TakeDroppodemos encontrar uma solução usando 40 bytes , Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&enquanto também tomamos a sequência ##a ser analisada como argumentos adicionais para Nest.
milhas
@miles. Muito bom uso de TakeDrop. E é melhor usar ##para inserir a sequência.
21416
1

APL, 23 21 caracteres

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

Sem a suposição (Graças a Dennis) e 1 caractere mais curto:

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

Experimente online .

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

Explicação: Há um padrão em como os elementos se movem quando são alterados aleatoriamente:

seja x o índice original

seja o novo índice

seja L o comprimento da matriz

  • y é o dobro x
  • se x for maior ou igual à metade de L, aumente y
  • mantenha y dentro dos limites da matriz

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

Isso pressupõe que as indicações começam em 0. Aqui está o código mais 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;
}  

veja ideona para casos de teste

Jack Munição
fonte
Sei que já faz mais de um ano, mas você pode jogar algumas 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 - sua resposta atual é 119 btw, não 109, portanto -12 bytes). Como você modifica a matriz de entrada, não há necessidade de retorná-la; portanto, você pode alterá-la para um vazio para reduzir bytes. Ah, e se você converter para um Java 8 lambda com currying você poderia torná-lo ainda mais curto: 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

Experimente online!

Como funciona

Nós (re) definimos o operador binário \para esta tarefa. Seja a uma matriz en um número inteiro não negativo.

Se n for positivo, embaralharemos a matriz. Isso é obtido remodelando-o em uma matriz de comprimento (a) ÷ 2 linhas e duas colunas. 'transpõe a matriz resultante, criando duas linhas e achatando o resultado com [:]. Como Julia armazena matrizes na ordem da coluna maior, isso entrelaça as duas linhas.

Depois, chamamos \recursivamente com os embaralhados a e n - 1 ( ~-n) como argumentos, realizando embaralhamentos adicionais. Uma vez que n atinge 0 , voltamos o valor atual de um .

Dennis
fonte
0

Pyke, 7 bytes

VDlec,s

Experimente aqui!

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
fonte
0

Na verdade, 15 bytes

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

Experimente online!

Explicação:

`;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
fonte
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).

Uso

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

Experimente online .

Titus
fonte