Estou procurando um algoritmo de uma passagem que calcule a paridade de uma permutação. Suponho que uma permutação de entrada seja dada pelo fluxo . A saída deve ser a paridade da permutação. A questão que me interessa é quanta memória um algoritmo determinístico deve usar. Existe algum algoritmo aleatório para o problema?π[1],π[2],⋯,π[n]π[1],π[2],⋯,π[n]
Eu sei que o número de inversões computadas em uma passagem usa a memória . O limite superior pode ser facilmente obtido com qualquer BST. O limite inferior é apresentado aqui: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622Θ(n)Θ(n)
Infelizmente, a prova do limite inferior do artigo não pode ser estendida ao caso de paridade (ou não é tão óbvio para mim).
Também sei que a paridade de computação em um pequeno espaço com acesso aleatório a uma permutação pode ser feita no tempo e na memória pelo algoritmo determinístico ou em tempo e memória por um aleatório. Consulte http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256O(nlogn)O(nregistro⁡n)O(log2n)O(registro2⁡n)O(nlogn)O(nregistro⁡n)O(logn)O(registro⁡n)
A idéia principal é que a paridade de uma permutação possa ser calculada pela fórmula , onde é o número de ciclos e é o tamanho. Os autores fazem a decomposição do ciclo de uma permutação. Assim, pode-se calcular facilmente o número de ciclos.sgn(π)=(−1)n−csgn(π)=(−1)n−cccnn
Alguém conhece um algoritmo eficaz ou limite inferior na memória para calcular a paridade no modelo de streaming? Algoritmos aleatórios melhores que moedas aleatórias também são interessantes para mim.
— Vsevolod Oparin
É interessante. Você poderia esboçar uma prova ou nomear um problema, que reduz à paridade?
@ András: Um algoritmo de O (n) space não funciona simplesmente mantendo o controle de quais elementos já foram vistos (digamos em um vetor de bits) e, em seguida, para cada novo elemento x adicionando a paridade do # de ainda a ser elementos vistos menores que x?
@laszlo seu limite superior agora parece mais convincente para mim do que meu argumento para um limite inferior maior. O(n)O(n)
Um resultado negativo para o limite inferior. Os autores do primeiro papel fornece permutação com base em dois conjuntos A e B . Eles o usam para calcular se A e B se cruzam. A paridade computacional da permutação requer apenas 3 bits de comunicação unidirecional. Pode ser facilmente obtido calculando a classificação da matriz correspondente. π=A0¯B1A0B1¯π=A0¯B1A0B1¯AABBAABB
Relacionados: stackoverflow.com/questions/20702782/...
Eu gostaria de pedir a todos que não votassem nisso, pois isso não é uma resposta, mas um comentário extenso, no qual gostaria de argumentar por que essa pergunta não recebeu nenhuma resposta. Meu ponto principal é que um limite inferior da complexidade da comunicação não funcionará. Com isso, quero dizer que não importa como cortamos a entrada em duas partes e a entregamos a dois jogadores, A e B, A pode transferir um único bit para B, a partir do qual ele pode calcular a paridade da permutação. (Isso se segue simplesmente considerando inversões.)
As provas que usam outro limite são difíceis. Veja este comentário aqui de Noam Nisan (para a versão não determinística): Limites no tamanho do menor NFA para L_k-distinct ,
essa pergunta relacionada, respondida por Hermann Gruber, que mostra que o limite inferior da complexidade da comunicação pode estar muito longe da verdade (novamente na versão não determinística) Limite inferior para a NFA que aceita linguagem de três letras .
Também relacionado que, para decidir se a permutação é um único ciclo, parece difícil, veja este artigo da FOCS de Ran Raz e Boris Spieker: http://www.computer.org/csdl/proceedings/focs/1993/4370/00 /0366870-abs.html .
Então, eu também estou muito interessado em aprender a resposta para esta pergunta.
Quando você diz que "não importa como cortamos a entrada em duas partes", seu argumento também exclui reduções quando a permutação é dividida em mais de duas partes? Por exemplo, no artigo vinculado sobre a contagem do número de inversões, há uma redução da disjunção definida, onde Alice e Bob têm entradas e formam permutações ¯ A 0 B 1 A 0 ¯ B 1 e ¯ A 1 B 0 A 1 ¯ B 0 . O índice 0 ou 1 refere-se às transformações 2 xA , B ⊆ [ n ]UMA,B⊆[n]UMA0 0¯B1 1UMA0 0B1 1¯UMA0 0¯B1 1UMA0 0B1 1¯UMA1 1¯B0 0UMA1 1B0 0¯UMA1 1¯B0 0UMA1 1B0 0¯2 x2xe , e a barra refere-se a complementação. Em outras palavras, e se a comunicação puder ser múltipla? 2 x + 12x+1 1
@laszlo: Neste problema, realmente não importa como você corta a entrada, desde que você a entregue apenas a dois jogadores, pois a paridade da permutação é determinada pelo número de seus ciclos (por isso é diferente do número inversões).
É fácil ver como A pode calcular um pouco de sua entrada usando qual B pode calcular a paridade? Vejo como A e B sabem o número de ciclos "dentro de suas partes". Mas como eles encontram a paridade do número de ciclos de "travessia"?
@laszlo: Suponha que a entrada de A seja algo como 1-> 7, 2-> 5, 3-> 8, 4-> 6. Isso tem o mesmo número de inversões que 1-> 5, 2-> 6, 3-> 8, 4-> 7. De maneira mais geral, B sabe em quais números os números de A são mapeados. Usando um número par de inversões, A pode permutar esses números em uma ordem crescente, exceto possivelmente nos dois últimos. A relação desses dois últimos números é a que ela envia.