Algorytm losowego ustawiania czasu w linijce w czasie

Czy istnieje algorytm tasowania karabinu liniowego w czasie? Jest to algorytm, który niektóre szczególnie sprawne ręce są w stanie wykonać: równomierne dzielenie tablicy wejściowej o równej wielkości, a następnie przeplatanie elementów dwóch połówek.

Mathworld ma krótką stronę na temat losowania karabinów . W szczególności interesuje mnie odmiana przetasowania, która przekształca tablicę wejściową 1 2 3 4 5 6 w 1 4 2 5 3 6. Zauważ, że w ich definicji długość wejściowa wynosi $2n$ .

Wykonanie tego w czasie liniowym jest proste, jeśli mamy pod ręką drugą tablicę o rozmiarze $n$ lub większym. Najpierw skopiuj ostatnie $n$ elementów do tablicy. Wtedy, zakładając, że indeksy 0 opartych skopiowanie pierwszego $n$ elementów z indeksów $[0,1,2,...,n-1]$ do $[0, 2, 4,...,2n-2]$ . Następnie skopiuj $n$Elementy z drugiej tablicy z powrotem do układu wejściowego, oznaczenia wskaźników $[0,1,2,...,n-1]$ do $[1,3,5,...,2n-1]$ . (Możemy wykonać nieco mniej pracy niż to, ponieważ pierwszy i ostatni element na wejściu się nie poruszają.)

Jednym ze sposobów próby wykonania tego w miejscu jest rozkład permutacji na rozłączne cykle, a następnie przestawienie elementów zgodnie z każdym cyklem. Ponownie, zakładając indeksowanie oparte na 0, permutacja występująca w przypadku 6 elementów wynosi

$$\sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}.$$

Zgodnie z oczekiwaniami, pierwszy i ostatni element są stałymi punktami, a jeśli permutujemy środkowe 4 elementy, otrzymujemy oczekiwany wynik.

Niestety moje rozumienie matematyki permutacji (i ich ) opiera się głównie na wikipedii i nie wiem, czy można tego dokonać w czasie liniowym. Może permutacje związane z tym tasowaniem można szybko rozłożyć? Ponadto nie potrzebujemy nawet pełnego rozkładu. Wystarczyło określić tylko jeden element każdego z rozłącznych cykli, ponieważ możemy zrekonstruować cykl z jednego z jego elementów. Być może konieczne jest zupełnie inne podejście.$\LaTeX$

Dobre zasoby związane z matematyką są tak samo cenne jak algorytm. Dzięki!

Problem jest zaskakująco nietrywialny. Oto fajne rozwiązanie Ellisa i Markova, In-Situ, Stable Scalanie za pomocą Perfect Shuffle (sekcja 7). Ellis, Krahn i Fan, Computing the Cycles in the Perfect Shuffle Permutation, wybrali „liderów cyklu” kosztem większej ilości pamięci. Powiązany jest także miły artykuł Ficha, Munro i Poblete, Permuting In Place , który daje ogólny algorytm czasowy n ) dla modelu wyroczni. Jeśli dostępna jest tylko wyrocznia dla permutacji, algorytm wymaga przestrzeni logarytmicznej; jeśli mamy także wyrocznię dla odwrotności, wymaga ona stałej przestrzeni.$O(n\log n)$

Teraz rozwiązanie Ellisa i Markowa. Najpierw załóżmy, że . Następnie obliczenie idealnego odtwarzania losowego aby n redukuje się do obliczania idealnego odtwarzania losowego zleceń x i y , przy obrocie ich poprzedniego. Oto dowód na przykładzie ( n = 5 , x = 3 , y = 2 ): 012 345 67 89 012 567 34 89 051627 $n = x+y$$n$$x$$y$$n=5$$x=3$$y=2$

$$\begin{array}{cc} 012\mathbf{345} & \mathbf{67}89 \\ 012\mathbf{567} & \mathbf{34}89 \\ 051627 & 3849 \end{array}$$

Ellis i Markov znaleźli łatwy sposób na obliczenie idealnego losowania, gdy , przy użyciu stałej przestrzeni i czasu liniowego. Korzystając z tego, otrzymujemy algorytm obliczania idealnego losowania dla dowolnego n . Najpierw zapisu n = 2 K 0 + ⋯ + 2 K W użyciu binarnego kodowania n i pozwolić n I = 2 k ı + ⋯ + 2 K wagowo . Obróć środkowy n 0 0 bitów. Ignorowanie prawej ręki $n=2^k$$n$$n = 2^{k_0} + \cdots + 2^{k_w}$$n$$n_i = 2^{k_i} + \cdots + 2^{k_w}$$n_0$ bitów, przetasuj prawą $2^{k_0}$ bitów obracać BliskiegoN-1bitów i Wtasować stroną2 K 1 bitów. I tak dalej. Zwróć uwagę, że obrót jest łatwy, ponieważ kilka pierwszych elementów obróconych działa jako linie wiodące cyklu. Całkowita złożoność obrotu wynosiO(n0+⋯+nw)=O(n), ponieważn t + 1 <nt/2. Całkowita złożoność tasowania wewnętrznego wynosiO$2^{k_0}$$n_1$$2^{k_1}$$O(n_0 + \cdots + n_w) = O(n)$$n_{t+1} < n_t/2$ .$O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$

Pozostaje pokazać, jak obliczyć idealne odtwarzanie losowe, gdy . W rzeczywistości, będziemy w stanie zidentyfikować liderów cyklu, po klasycznej pracy na naszyjniki (Fredricksen i Maiorana, naszyjniki z koralików w k kolorów i k -ary de Bruijn sekwencji ; Fredricksen i Kessler, algorytm generowania kolie paciorków w dwóch kolorach ).$n=2^k$$k$$k$

Jakie jest połączenie? Twierdzę, że permutacja losowa odpowiada przesunięciu w prawo reprezentacji binarnej. Oto przykład na dowód, dla : 000 001 010 011 100 101 110 111 000 100 001 101 010 110 011 111 Dlatego, aby znaleźć liderów cyklu, musimy znaleźć jednego przedstawiciela z każdej klasy równoważności obrotu ciągi binarne o długości k . W powyższych pracach podano następujący algorytm generowania wszystkich liderów cyklu. Zacznij od 0 $n=8$

$$\begin{array}{cccccccc} 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 000 & 100 & 001 & 101 & 010 & 110 & 011 & 111 \end{array}$$ $k$$0^k$. Na każdym kroku, jesteśmy w pewnym momencie 0 , nowy ciąg znaków jest liderem cyklu. . Znajdź maksymalny indeks i bitu zerowego, podziel k przez i, aby otrzymać k = d ⋅ i + r , i niech następujący punkt będzie ( a 1 … a i - 1 1 ) d a 1 … a r . Ilekroć r $a_1 \ldots a_k$$i$$k$$i$$k = d\cdot i + r$$(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$$r = 0$

Na przykład, gdy generuje to sekwencję 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111$n=16$

$$\mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011}, \mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}.$$

Liderzy cyklu są podświetleni.

To było pierwsze pytanie na cs.stackexchange.com, a odpowiedź jest tutaj: /cs/332/in-place-alameterm-for-interleaving-an-array/400#400

Jest to wyjaśnienie artykułu: http://arxiv.org/abs/0805.1598 .

$k$$2$$k$$3^2$$k=2$

$j \to 2j \mod 2n+1$

Co się stanie, jeśli zapiszesz losowanie riffle jako funkcję? Gdyby$m$ jest długością całkowitej tablicy, let $n = m-2$być długością tablicy po usunięciu pierwszego i ostatniego elementu. Następnie przetasowany indeks indeksu$i$ jest $f(i) = 2\cdot i$ gdyby $i \leq n/2$ i $f(i) = 2 \cdot (i \mod n/2) - 1$ gdyby $i > n/2$. Następnie możesz po prostu „przeskoczyć wskaźnik” przez tablicę, zamieniając przez ponowne zastosowanie funkcji.

Zakładając losowy dostęp, byłby to czas liniowy, który byłby wymagany $O(1)$ dodatkowe słowa (do przechowywania wartości tablicy w danym indeksie) i tak dalej $O(\log n)$ dodatkowa przestrzeń.