Jak iterować po wektorach w kolejności prawdopodobieństwa na małej przestrzeni

Rozważmy wymiarowy wektor gdzie . Dla każdego wiemy i załóżmy, że są niezależne. Wykorzystując te prawdopodobieństwa, czy istnieje skuteczny sposób na iterację binarnych wektorów wymiarowych w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego (z dowolnymi wyborami wiązań) z wykorzystaniem przestrzeni podliniowej w wielkości wyjściowej? v v i ∈ { 0 , 1 } i p i = P ( v i = 1 ) v i$n$$v$$v_i \in \{0,1\}$$i$$p_i = P(v_i = 1)$$v_i$$n$

Weźmy na przykład . Najbardziej prawdopodobny wektor to a najmniej prawdopodobne to . ( 1 , 0 , 1 ) { 0 , 1 , 0 $p = \{0.8, 0.3, 0.6\}$$(1,0,1)$$\{0,1,0\}$

W przypadku bardzo małej liczby możemy oznaczyć każdy z wektorów prawdopodobieństwem i po prostu posortować, ale to oczywiście nie użyłoby przestrzeni podliniowej.2 $n$$2^n$

Dokładny wariant tego pytania został wcześniej zadany na stronie /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .

Poniżej podano algorytm, który wykorzystuje około czasu i przestrzeni.2 n /$2^n$$2^{n/2}$

Najpierw spójrzmy na problem sortowania sum wszystkich podzbiorów elementów.$n$

Zastanów się nad tym podproblemem: masz dwie posortowane listy o długości i chciałbyś stworzyć posortowaną listę sum par liczb na listach. Chciałbyś to zrobić w przybliżeniu w czasie (rozmiar wyjściowy), ale w przestrzeni podliniowej. Możemy osiągnąć przestrzeń . Trzymamy kolejkę priorytetową i wyciągamy sumy z kolejki priorytetowej w kolejności rosnącej.O ( m 2 ) O ( m $m$$O(m^2)$$O(m)$

Niech wykazy być 1 ... a m i b 1 ... b m , sortowane w porządku rosnącym. Bierzemy m sum a i + b 1 , i = 1 … m i umieszczamy je w kolejce priorytetowej.$a_1 \ldots a_m$$b_1 \ldots b_m$$m$$a_i + b_1$$i = 1 \ldots m$

Teraz, gdy wyciągniemy najmniejszą pozostałą sumę z kolejki priorytetowej, jeśli j < m , wówczas umieszczamy sumę a i + b j + 1 w kolejce priorytetowej. W przestrzeni dominuje kolejka priorytetowa, która zawsze zawiera najwyżej m sum. Czas to O ( m 2 log m ) , ponieważ używamy O ( log m ) dla każdej operacji kolejki priorytetowej. To pokazuje, że możemy zrobić podproblem w O ( m $a_i + b_j$$j < m$$a_i + b_{j+1}$$m$$O(m^2 \log m)$$O(\log m)$ czas i przestrzeń O ( m ) .$O(m^2 \log m)$$O(m)$

Teraz, aby uporządkować sumy wszystkich podzbiorów liczb, po prostu korzystać z tego podprogramu gdzie lista I jest zbiorem sumy podzbiorów pierwszej połowie pozycji, a lista b I jest zbiorem sumy podzbiorów drugiej połowy przedmiotów. Możemy znaleźć te listy rekurencyjnie za pomocą tego samego algorytmu.$n$$a_i$$b_i$

Rozważymy teraz oryginalny problem. Niech będzie zbiorem współrzędnych, które są 0 , a S 1 będzie zbiorem współrzędnych, które są 1 . Następnie ∏ i ∈ S 0 p ( v i = 0 ) ∏ i ∈ S 1 p ( v i = 1 $S_0$$0$$S_1$$1$

$$\begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &=& \prod_{1\leq i \leq n} p(v_i=0) \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &=& \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}$$

Sortowanie tych liczb jest takie samo jak sortowanie liczb , więc zredukowaliśmy problem do sortowania sum podzbiorów n elementów.$\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$$n$

Możemy to zrobić w przestrzeni (jeśli nie zależy nam na czasie działania).$O(n)$

1. Dla danego ciągu możemy obliczyć w przestrzeni O ( n ) liczbę r ( x ) ciągów, które są bardziej prawdopodobne niż x ; to znaczy liczba x ′ st p ( x ′ ) > p ( x ) : wystarczy przejrzeć wszystkie x ′ ∈ { 0 , 1 } n i policzyć liczbę x ′ st$x \in \{0,1\}^n$$O(n)$$r(x)$$x$$x'$$p(x') > p(x)$$x'\in \{0,1\}^n$$x'$ . Zauważ, że r ( x ) to kolejny numer ciągu x na wyjściu.$p(x') > p(x)$$r(x)$$x$
2. Dla każdego możemy znaleźć x z r ( x ) = k w przestrzeni O ( n ) : przejrzyj wszystkie x ∈ { 0 , 1 } n , dla każdego x obliczenia r ( x ) , zatrzymaj i wyjmij x, jeśli r ( x ) = k .$k$$x$$r(x) = k$$O(n)$$x \in \{0,1\}^n$$x$$r(x)$$x$$r(x) = k$
3. Teraz wystarczy przejrzeć wszystkie od 0 do 2 n - 1 , dla każdego k drukuj x z r ( x ) = k .$k$$0$$2^n-1$$k$$x$$r(x) =k$

(Powinniśmy również zadbać o możliwe powiązania, ale nie jest to trudne).

Edycja: ta odpowiedź jest niepoprawna. Zobacz komentarze, aby uzyskać szczegółowe informacje. ~ gandaliter

Liniowy na wyjściu oznacza . Myślę, że oczywisty algorytm wykorzystuje tylko przestrzeń O ( n ) , oczywiście poza samym wyjściem.$O(2^n)$$O(n)$

1. Weź listę zawierającą pary i posortuj ją według | 0,5 - p i | , najpierw największy.$(i, p_i)$$\left|0.5 - p_i\right|$

2. Zdefiniuj podwójnie rekurencyjną funkcję, która pobiera listę takich par i częściowo wypełnionego wektora , ustawia wartość v i na 1, jeśli p i > 0,5 , a 0 w przeciwnym razie, i powtarza (używając końca listy i v ) , następnie odwraca v i powtarza się ponownie. Jeśli lista jest pusta, zamiast tego wyprowadza v .$v$$v_i$$1$$p_i > 0.5$$0$$v$$v_i$$v$

3. Wywołaj tę funkcję rekurencyjną na posortowanej liście i pustym wektorze.

Intuicja polega na tym, że najpierw ustawiasz wartości najbardziej pewnych elementów w wektorze (tych, których prawdopodobieństwa są najbliższe i 1 ), i wypełniasz wektor w ten sposób, kończąc na tych, których prawdopodobieństwa są najbliższe 0,5 . Każda możliwa wartość, jaką może przyjąć cały wektor, jest wyprowadzana w kolejności prawdopodobieństwa.$0$$1$$0.5$

Czas działania wynosi , co stanowi dolną granicę, ponieważ jest to długość wyniku. Złożoność przestrzeni wynosi O ( n ), ponieważ sortowanie nie wymaga więcej, a długość rekurencyjna to długość wektora, który wynosi n . Uważam, że jest to również dolna granica, ponieważ musi istnieć inny stan w pamięci dla każdego kroku działania algorytmu, a złożoność czasu wynosi O ( 2 n ) . Stany O ( n ) w pamięci są wymagane do wyliczenia O ( 2 n$O(2^n)$$O(n)$$n$$O(2^n)$$O(n)$$O(2^n)$kroki czasowe. Dlatego algorytm ten jest optymalizowany w najgorszym przypadku.