Existe um algoritmo de "classificação" que retorna uma permutação aleatória ao usar um comparador de troca de moedas?

9

Inspirada nesta pergunta em que o solicitante deseja saber se o tempo de execução muda quando o comparador usado em um algoritmo de pesquisa padrão é substituído por um lançamento justo, e também pela falha proeminente da Microsoft em escrever um gerador de permutação uniforme, minha pergunta é assim :

Existe um algoritmo de classificação baseado em comparação que, dependendo da nossa implementação do comparador:

  1. retorne os elementos em ordem classificada ao usar um comparador verdadeiro (ou seja, a comparação faz o que esperamos em um algoritmo de classificação padrão)
  2. retorna uma permutação uniformemente aleatória dos elementos quando o comparador é substituído por uma troca de moeda justa (ou seja, retorna x < y = truecom probabilidade 1/2, independentemente do valor de xey)

O código para o algoritmo de classificação deve ser o mesmo. É apenas o código dentro da "caixa preta" de comparação que pode mudar.

Joe
fonte
Veja também esta pergunta .
Raphael
2
Consulte também a seguinte pergunta interessante: cstheory.stackexchange.com/questions/5321/… .
Yuval Filmus 21/03
11
Deseja que seu comparador aleatório seja bem-comportado? Aqui estão duas maneiras possíveis. (1) Depois que o comparador decide que , sempre, e também . (2) A mesma, mas, além disso, se o comparador decide que e , em seguida, ele compromete-se (e ). Nos dois casos, cada consulta irrestrita ainda é completamente aleatória. x < y y > x x < y y < z x < z z > xx<yx<yy>xx<yy<zx<zz>x
Yuval Filmus 21/03/2013
@YuvalFilmus Eu quero essencialmente o que é solicitado em sua pergunta vinculada, exceto que o mesmo circuito também deve ser ordenado se substituirmos o gate aleatório por um gate de troca de comparação que ordene o par de elementos.
21313 Joe
11
Veja aqui para obter boas visualizações.
Raphael

Respostas:

3

O seguinte algoritmo determinístico (sem o comparador) funciona para uma tupla de entrada :(a1,,an)

  1. Faça o Fisher-Yates embaralhar usando seu comparador com algum par estático (dizer ) como um coin flip (fazendo amostragem de aceitação-rejeição). Se o comparador emitir 1 pela primeira vez, use-o invertido para evitar um ciclo de rejeição sem fim no caso determinístico.a1<a21
  2. (aceleração opcional: tente um único par vezes, em que n é o comprimento ou sua entrada. Se duas das saídas diferirem, retorne a permutação obtida em (1))nn
  3. Classifique sua matriz usando a classificação de mesclagem.

Dada uma relação de ordem determinística como comparador, esse algoritmo classifica uma matriz no tempo pois o embaralhamento de Fisher-Yates é executado em O ( n ) usando "bits aleatórios" não aleatórios máximos de O ( log n ) (por exemplo, chamadas para o seu comparador ) em cada etapa e classificação de mesclagem tem a mesma complexidade assintótica. O resultado de (1) é totalmente inútil neste caso, mas, como é seguido por uma espécie real, isso não faz mal.O(nlogn)O(n)O(logn)

Dado um giro real da moeda, pois o comparador (1) permite a matriz com igual probabilidade para cada permutação e se você realmente tiver que fazer (3) (você deixou de fora (2) ou (2) falhou em determinar a aleatoriedade)), isso não é verdade. dano porque a distribuição de seu resultado depende apenas da ordem de sua entrada, que é distribuída uniformemente entre todas as permutações por causa de (1); portanto, o resultado de todo o algoritmo também é uniformemente distribuído. O número de vezes que cada amostragem de aceitação-rejeição deve ser repetida é distribuído geometricamente (rejeitar com probabilidade ) e, portanto, tem um valor esperado<2. Cada repetição usa no máximobits delogn, portanto, a análise de tempo de execução é quase a mesma do caso determinístico, mas obtemos apenas umtempodeexecução esperadodeO(nlogn), com a possibilidade de não terminação (termina comquase certeza).<12<2lognO(nlogn)


Como Joe apontou: Se você não gostar do teste do primeiro bit em (1), faça (3) e depois (1) e use que sempre é 0 , pois a matriz já está classificada no caso determinístico. Além disso, você deve subtrair seu número aleatório do limite superior do intervalo no loop, porque o limite superior do número aleatório gera a permutação idêntica. Mas lembre-se de que (2) é proibido, pois você sempre deve fazer o embaralhamento no caso de resgate.an<a10


Você pode até usar as mesmas chamadas para o seu comparador para (1) e (3), mas provar que o resultado é distribuído uniformemente é pelo menos muito mais difícil, se possível.


O algoritmo a seguir não possui fases distintas para ordenar e ordenar, mas é assintoticamente mais lento. É essencialmente tipo de inserção com pesquisa binária . Vou usar para indicar a entrada e b k = ( b k , 1 , ... , b k , k ) para indicar o resultado após o k -ésimo rodada:a=(a1,,an)bk=(bk,1,,bk,k)k

  1. Defina b1,1=a1
  2. Se então b 2 = ( a 2 , a 1 ) e ( c , d ) : = ( 2 , 1 ) else b 2 = ( a 1 , a 2 ) e ( c , d ) : = ( 1 , 2 ) . Em ambos os casos, um d <a2<a1b2=(a2,a1)(c,d):=(2,1)b2=(a1,a2)(c,d):=(1,2) sempre será 0 (ou seja, falso) para um comparador não aleatório.ad<ac0
  3. Para obter para k 3, obtenha b k - 1 primeiro.bkk3bk1
  4. Deixe- e k ' = 2, l , ou seja, k ' é a menor potência de 2 não menor do que k .l=log2kk=2lk2k
  5. i0=0j{1,,l}
    ij={ij1+2ljij1+2lj>k1ad<acij1ij1+2lj>k1¬(ad<ac)ij1+2ljij1+2ljk1bk1,ij1+2lj<akij1ij1+2ljk1¬(bk1,ij1+2lj<ak)
  6. il>kbk=(bk1,1,,bk1,il1,ak,bk1,il,,bk1,k1)
  7. bn

k1k

Observe que esse algoritmo é ineficiente em ambos os modos, comparado à ordenação aleatória e mesclada de Fisher-Yates, pois inserir um elemento em uma posição arbitrária é caro se o uso de uma matriz e a pesquisa binária precisar de tempo linear ao usar uma lista. Mas talvez uma modificação da classificação da pilha ou da árvore de maneira semelhante possa levar a um algoritmo mais rápido.

frafl
fonte
@ Joe, você pode colocar todos os seus pontos ainda válidos para a publicação na forma atual em um comentário e excluir o restante?
Frafl 21/03
Eu esperava um algoritmo que não execute etapas diferentes, dependendo do comparador usado. Você pode evitar um loop infinito de rejeição sem investigar o comparador? Eu acho que você poderia evitar a rejeição por executar o passo (3), primeiro ...
Joe
i
Primeiro comentário: observe que eu não jogo fora o primeiro bit de amostra, é "uso duplo". Pensei em inverter cada segundo bit, mas isso não impediria o loop infinito. De fato, é necessário algum padrão irregular e até pode rejeitar muito mais entradas. É claro que eu poderia XOR os dois bits mais recentes em vez do primeiro e o mais recente, mas isso não é realmente diferente.
precisa saber é
ian<a10
4

n2A/2B1/n!n>21/n!A/2B

Yuval Filmus
fonte
11
Mas isso só vale se precisarmos de um limite determinístico no tempo de execução, que não foi solicitado na pergunta. Se exigirmos apenas que o tempo de execução esperado seja finito, isso não deve ser problema.
Frafl 21/03
11
Você conhece algum algoritmo de classificação razoável que não termine em tempo polinomial?
Yuval Filmus
2
Você mistura o caso determinístico e aleatório. O algoritmo pode terminar em tempo polinomal determinístico se chamado com uma relação de ordem determinística e em tempo polinomial esperado se chamado com uma moeda como comparador.
Frafl 21/03
2k
kA/2k