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

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.

O seguinte algoritmo determinístico (sem o comparador) funciona para uma tupla de entrada :$(a_1,\dots,a_n)$

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.$a_1 < a_2$$1$
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))$n$$n$
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.$\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

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).$< \frac{1}{2}$$< 2$$\log n$$\mathcal{O}(n \log n)$

---

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.$a_n < a_1$$0$

---

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=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Defina $b_{1,1} = a_1$
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$a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$ sempre será 0 (ou seja, falso) para um comparador não aleatório.$a_d < a_c$$0$
3. Para obter para k ≥ 3, obtenha b k - 1 primeiro.$b_{k}$$k \geq 3$$b_{k-1}$
4. Deixe- e k ' = 2, l , ou seja, k ' é a menor potência de 2 não menor do que k .$l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
5. $i_0 = 0$$j \in \{1,\dots,l\}$ $$i_j = \begin{cases} i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} > k-1 \wedge a_d < a_c\\ i_{j-1} & i_{j-1} + 2^{l-j} > k-1 \wedge \neg (a_d < a_c)\\ i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} \leq k-1 \wedge b_{k-1,i_{j-1} + 2^{l-j}} < a_k \\ i_{j-1} & i_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b_{k-1,i_{j-1} + 2^{l-j}} < a_k) \\ \end{cases}$$
6. $i_l > k$$b_k=(b_{k-1,1},\dots,b_{k-1,i_l -1},a_k,b_{k-1,i_l},\dots,b_{k-1,k-1})$
7. $b_n$

$k-1$$k$

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.

$n \leq 2$$A/2^B$$1/n!$$n > 2$$1/n!$$A/2^B$