Algoritmo linear de riffle shuffle no tempo linear

15

Existe um algoritmo linear de riffle shuffle no tempo linear? Este é o algoritmo que algumas mãos especialmente hábeis são capazes de executar: dividir uniformemente uma matriz de entrada de tamanho uniforme e depois intercalar os elementos das duas metades.

Mathworld tem uma breve página sobre riffle shuffle . Em particular, estou interessado na variedade de saída aleatória que transforma a matriz de entrada 1 2 3 4 5 6 em 1 4 2 5 3 6. Observe que em sua definição, o comprimento da entrada é 2n .

É fácil fazer isso em tempo linear se tivermos uma segunda matriz de tamanho n ou mais útil. Primeiro copie os últimos n elementos para a matriz. Então, supondo que a indexação baseado em 0, copiar os primeiros n elementos de índices de [0,1,2,...,n1] a . Em seguida, copie os elementos da segunda matriz de volta para a matriz de entrada, mapeando os índices paran [ 0 , 1 , 2 , . . . , N - 1 ] [ 1 , 3 , 5 , . . . , 2 n - 1 ][0,2,4,...,2n2]n[0,1,2,...,n1][1,3,5,...,2n1]. (Podemos trabalhar um pouco menos que isso, porque o primeiro e o último elementos da entrada não se movem.)

Uma maneira de tentar fazer isso no local envolve a decomposição da permutação em ciclos disjuntos e, em seguida, reorganizar os elementos de acordo com cada ciclo. Novamente, assumindo a indexação baseada em 0, a permutação envolvida no caso de 6 elementos é

σ=(012345024135)=(0)(5)(1243).

Como esperado, o primeiro e o último elementos são pontos fixos e, se permutarmos os 4 elementos do meio, obtemos o resultado esperado.

Infelizmente, meu entendimento da matemática das permutações (e seus ) é baseado principalmente na wikipedia, e não sei se isso pode ser feito em tempo linear. Talvez as permutações envolvidas nesse embaralhamento possam ser rapidamente decompostas? Além disso, nem precisamos da decomposição completa. Apenas determinar um único elemento de cada um dos ciclos separados seria suficiente, pois podemos reconstruir o ciclo a partir de um de seus elementos. Talvez seja necessária uma abordagem completamente diferente.LATEX

Bons recursos na matemática relacionada são tão valiosos quanto um algoritmo. Obrigado!

Johny
fonte
Existe uma solução de tempo (com O ( 1 ) espaço extra). Não conheço nenhuma solução de tempo linear. O(nlgn)O(1)
Radu GRIGore #
4
Isso é mais apropriado para cs.stackexchange. No modelo não uniforme, vezes é sempre possível. Nesse caso, deve ser possível de maneira uniforme. O(n)
Yuval Filmus
1
@ Radu Semelhante a esta pergunta , esse problema provavelmente não tem uma solução usando apenas espaço extra, mas O ( log n ) espaço extra. O(1)O(logn)
Tyson Williams
2
Retiro meu comentário (e voto para fechar)! (Embora a pergunta é respondida na literatura.)
Yuval Filmus
1
Eu ouvi essa pergunta de um estudante de CS na semana passada, que a ouviu em uma entrevista de emprego.
Jeffε

Respostas:

12

O problema é surpreendentemente não trivial. Aqui está uma ótima solução de Ellis e Markov, fusão in situ e estável por meio do Perfect Shuffle (seção 7). Ellis, Krahn e Fan, computando os ciclos na permutação aleatória perfeita, conseguem selecionar "líderes de ciclo", à custa de mais memória. Também está relacionado o belo artigo de Fich, Munro e Poblete, Permuting In Place , que fornece um algoritmo geral de tempo para o modelo oracle. Se apenas um oráculo para a permutação estiver disponível, o algoritmo requer espaço logarítmico; se também temos um oráculo para o inverso, isso requer espaço constante.O(nlogn)

Agora, a solução de Ellis e Markov. Primeiro, suponha que . Em seguida o cálculo do baralhamento perfeito de ordem n reduz a computar a aleatória perfeito de ordens x e y , com uma rotação que precede as mesmas. Aqui está uma prova por exemplo ( n = 5 , x = 3 , y = 2 ): 012 345 67 89 012 567 34 89 051627 3849n=x+ynxyn=5x=3y=2

012345678901256734890516273849

Ellis e Markov encontraram uma maneira fácil de calcular o shuffle perfeito quando , usando espaço constante e tempo linear. Usando isso, obtemos um algoritmo para calcular o shuffle perfeito para n arbitrário . Primeiro, escreva n = 2 k 0 + + 2 k w usando a codificação binária de n e deixe n i = 2 k i + + 2 k w . Gire o meio n 0 bits, embaralhe o lado direito 2 kn=2knn=2k0++2kwnni=2ki++2kwn0 bits. Ignorando os2 k 0 bitsà direita, gire osn1bitsdo meioe embaralhe os2 k 1 bitsà direita. E assim por diante. Observe que a rotação é fácil, pois os primeiros elementos rotacionados funcionam como líderes de ciclo. A complexidade total da rotação éO(n0++nw)=O(n), uma vez quen t + 1 <nt/2. A complexidade total dos shuffles internos éO(2k02k0n12k1O(n0++nw)=O(n)nt+1<nt/2 .O(2k0++2kw)=O(n)

Resta mostrar como calcular o shuffle perfeito quando . Na verdade, vamos ser capazes de identificar líderes de ciclo, seguindo trabalho clássico sobre colares (Fredricksen e Maiorana, colares de contas em k cores e k -ary de seqüências de Bruijn ; Fredricksen e Kessler, Um algoritmo para gerar colares de contas em duas cores )n=2kkk

Qual é a conexão? Afirmo que a permutação aleatória corresponde à mudança correta da representação binária. Aqui está uma prova por exemplo, para : 000 001 010 011 100 101 110 111 000 100 001 101 010 110 011 111 Portanto, para encontrar líderes de ciclo, precisamos encontrar um representante de cada classe de equivalência da rotação de cadeias binárias de comprimento k . Os documentos mencionados acima fornecem o seguinte algoritmo para gerar todos os líderes de ciclo. Comece com 0 kn=8

000001010011100101110111000100001101010110011111
k0k. A cada passo, estamos em algum momento . Encontre o índice máximo i de um bit zero, divida k por i para obter k = d i + r e deixe o seguinte ponto ser ( a 1a i - 1 1 ) d a 1a r . Sempre que r = 0 , a nova sequência é um líder de ciclo.a1akikik=di+r(a1ai11)da1arr=0

Por exemplo, quando isso gera a sequência 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111 , 1111 .n=16

0000,0001,0010,0011,0101,0110,0111,1111.

Os líderes do ciclo são destacados.

Yuval Filmus
fonte
3
Veja também a resposta de Aryabhata, que usa arxiv.org/abs/0805.1598 . Esse artigo, "Um algoritmo simples no local para reprodução aleatória" de Jain, usa a mesma idéia, mas, em vez dos poderes de , usa poderes de 3 . O ponto é que, como 2 é um módulo raiz primitivo de 3 k , é fácil ver que 3 0 , , 3 k são líderes de ciclo. Ainda mais simples que Ellis e Markov! 2323k30,,3k
Yuval Filmus
Embora eu ache o artigo de Jain um pouco mais direto, estou preferindo o artigo anterior, bem como o post anterior com mais votos.
Johny
6

Esta foi uma pergunta de propagação em cs.stackexchange.com e uma resposta está aqui: /cs/332/in-place-algorithm-for-interleaving-an-array/400#400

É uma explicação do artigo: http://arxiv.org/abs/0805.1598 .

k2k32k=2

j2jmod2n+1

Aryabhata
fonte
Ha! Eu esqueci completamente dessa pergunta, mesmo se eu participasse da discussão. Isso significa que eu realmente não entendi como funciona naquele momento.
Radu GRIGore
2

O que acontece se você escrever o shuffle de rifles como uma função? E sem é o comprimento da matriz total, deixe n=m-2seja o comprimento da matriz após remover o primeiro e o último elemento. Em seguida, o índice embaralhado do índiceEu é f(Eu)=2Eu E se Eun/2 e f(i)=2(imodn/2)1 if i>n/2. Then you can just "pointer jump" through the array, swapping by re-applying the function.

Assuming random access, this would be linear time while requiring O(1) extra words (for storing the value of the array at any given index), and so O(logn) extra space.

Robert Robere
fonte
Ah, wait. This assumes that all of the values in the riffle permutation lie on the same cycle. This strategy would have to be modified a bit, depending on how many disjoint cycles there are.
Robert Robere