Czy istnieje algorytm „sortowania”, który zwraca losową permutację podczas korzystania z komparatora z monetą?

Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie jest zatem :

Czy istnieje algorytm sortowania oparty na porównaniu, który w zależności od naszej implementacji komparatora:

1. zwracaj elementy w posortowanej kolejności, gdy używasz prawdziwego komparatora (tzn. porównanie robi to, czego oczekujemy od standardowego algorytmu sortowania)
2. zwraca jednolicie losową permutację pierwiastków, gdy komparator jest zastąpiony przez uczciwą rzut monetą (tzn. zwraca x < y = truez prawdopodobieństwem 1/2, niezależnie od wartości x i y)

Kod algorytmu sortowania musi być taki sam. Tylko kod w „czarnej skrzynce” porównania może ulec zmianie.

Poniższy algorytm deterministyczny (bez komparatora) działa dla krotki wejściowej :$(a_1,\dots,a_n)$

1. Wykonaj tasowanie Fisher-Yates za pomocą komparatora z parą statyczną (powiedz ) jako rzut monetą (próbkowanie przy odrzucaniu-odrzucaniu). Jeśli komparator wyprowadza za pierwszym razem, użyj go odwróconego, aby uniknąć nieskończonej pętli odrzucania w przypadku deterministycznym.$a_1 < a_2$$1$
2. (opcjonalne przyspieszenie: Wypróbuj pojedynczą parę razy, gdzie jest długością lub wartością wejściową. Jeśli dowolne dwa wyjścia różnią się, zwróć permutację uzyskaną w (1))$n$$n$
3. Posortuj tablicę za pomocą sortowania scalającego.

Biorąc pod uwagę deterministyczną relację porządku jako komparator, ten algorytm sortuje tablicę w czasie ponieważ losowanie Fisher-Yates działa w przy użyciu maximal nielosowe „losowe bity” (np. wywołania do twojego komparatora) na każdym kroku i sortowanie według scalania ma tę samą asymptotyczną złożoność. Wynik (1) jest w tym przypadku całkowicie bezużyteczny, ale ponieważ następuje po nim prawdziwy rodzaj, nie szkodzi.$\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

Biorąc pod uwagę prawdziwy rzut monetą, ponieważ komparator (1) permutuje tablicę z jednakowym prawdopodobieństwem dla każdej permutacji, a jeśli naprawdę musisz zrobić (3) (pominąłeś (2) lub (2) nie udało się ustalić losowości), to nie jest szkoda, ponieważ rozkład jego wyniku zależy tylko od kolejności jego wejścia, która jest równomiernie rozłożona między wszystkimi permutacjami z powodu (1), więc wynik całego algorytmu jest również równomiernie rozłożony. Liczba powtórzeń każdego próbkowania akceptacji-odrzucenia jest rozkładem geometrycznym (odrzucenie z prawdopodobieństwem ), a zatem ma wartość oczekiwaną . Każde powtórzenie wykorzystuje maksymalnie bitów, więc analiza czasu wykonywania jest prawie taka sama jak w przypadku deterministycznym, ale otrzymujemy tylko$< \frac{1}{2}$$< 2$$\log n$oczekiwany czas działania , z możliwością nieterminacji (kończy się prawie na pewno ).$\mathcal{O}(n \log n)$

---

Jak wskazał Joe: Jeśli nie podoba ci się test dla pierwszego bitu w (1), zrób (3), a następnie (1) i użyj który zawsze wynosi , ponieważ tablica jest już posortowana w przypadku deterministycznym . Dodatkowo musisz odjąć swoją liczbę losową od górnej granicy zakresu w pętli, ponieważ górna granica liczby losowej daje identyczną permutację. Pamiętaj jednak, że (2) jest wtedy zabronione, ponieważ zawsze musisz wykonać losowanie w przypadku okupu.$a_n < a_1$$0$

---

Możesz nawet użyć tych samych wywołań do komparatora dla (1) i (3), ale udowodnienie, że wynik jest równomiernie rozłożony, jest co najmniej o wiele trudniejsze, o ile w ogóle możliwe.

---

Poniższy algorytm nie ma odrębnych faz do losowego sortowania i sortowania, ale jest asymptotycznie wolniejszy. Jest to w zasadzie sortowanie przez wstawianie z wyszukiwaniem binarnym . Będzie używać do oznaczenia wejściowe i dla określenia rezultatu po -tym etap:$a=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Ustaw$b_{1,1} = a_1$
2. Jeśli to i inaczej i . W obu przypadkach będzie zawsze wynosić (tj. Fałsz) dla nielosowego komparatora.$a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$$a_d < a_c$$0$
3. Aby uzyskać dla najpierw uzyskaj .$b_{k}$$k \geq 3$$b_{k-1}$
4. Niech i , tzn. jest najmniejszą potęgą nie mniejszą niż .$l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
5. Niech . Dla każdego niech $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. Jeśli powtórz (5.) else$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. Wyjście$b_n$

Przypadek losowy: 5 + klauzula if z 6 jest w zasadzie próbką akceptacji-odrzucenia. Reszta algorytmu jest naiwnym tasowaniem: przetasuj pierwsze elementy i dodaj ty element do każdej pozycji z jednakowym prawdopodobieństwem. Gdybyśmy użyli normalnego sortowania wstawiania, otrzymalibyśmy zamiast tego rozkład dwumianowy.$k-1$$k$

Zauważ, że ten algorytm jest nieefektywny w obu trybach w porównaniu do sortowania i łączenia przez Fisher-Yatesa, ponieważ wstawianie elementu do dowolnej pozycji jest kosztowne, jeśli użycie tablicy i wyszukiwanie binarne wymaga czasu liniowego, jeśli używasz listy. Ale być może modyfikacja sortowania sterty lub sortowania drzewa w podobny sposób może prowadzić do szybszego algorytmu.

Nie, jest to niemożliwe, chyba że . Prawdopodobieństwo, że algorytm generujący permutację jest generowany za pomocą losowego komparatora, ma charakter dyadyczny, tzn. Ma postać , natomiast prawdopodobieństwo powinno wynosić. Gdy , nie ma sposobu na napisanieW formie .$n \leq 2$$A/2^B$$1/n!$$n > 2$$1/n!$$A/2^B$