Jak skutecznie produkować wszystkie sekwencje binarne o równej liczbie zer i jedynek?

Binarnej sekwencji o długości $n$ właśnie uporządkowaną sekwencję $x_1,\ldots,x_n$ , tak że każdy $x_j$ oznacza albo $0$ lub $1$ . Aby wygenerować wszystkie takie sekwencje binarne, można użyć oczywistej struktury drzewa binarnego w następujący sposób: katalog główny jest „pusty”, ale każde lewe dziecko odpowiada dodaniu $0$ do istniejącego łańcucha, a każde prawe dziecko $1$ . Teraz każda sekwencja binarna jest po prostu ścieżką o długości $n+1$ rozpoczynającą się od nasady i kończącą się na liściu.

Oto moje pytanie:

Możemy zrobić lepiej, jeśli chcemy tylko, aby wygenerować wszystkie binarne ciągi o długości $2n$ , które mają dokładnie $n$ zer i $n$ te?

Przez „czy możemy zrobić lepiej”, mam na myśli, że powinniśmy mieć mniejszą złożoność niż głupiutki algorytm, który najpierw buduje całe drzewo powyżej, a następnie próbuje znaleźć ścieżki o równej liczbie „lewej” i „prawej” krawędzi.

algorithms graphs binary-trees

— Vidit Nanda
źródło

Czy potrafisz znaleźć sposób na skuteczne wygenerowanie wszystkich ściśle rosnących sekwencji

liczb w zakresie od 1 do

n

$n$

2 n

$2n$

— Cornelius Brand

Nie mogę komentować złożoności, ale mój naiwny algorytm generowałby spacery wzdłuż krawędzi kwadratowej siatki od jednego rogu do ukośnego, używając pewnego rodzaju schematu cofania. Oznacza to, że 01 i 10 kończą w tej samej pozycji (w przeciwieństwie do twojego drzewa), ale dzięki cofnięciu znamy tę historię.

— Hendrik Jan

Z prawdopodobnie innej uwagi, oto implementacja Java

-iterator

(\binom{n}{k})

${n \choose k}$ .

— Pål GD

Odpowiedzi:

Oczywiście istnieją ciągów binarnych o długości . Aby przejść przez plik binarny, algorytm musi odwiedzić każdy węzeł raz, tzn. Musi wykonać $4^{n}$ $2n$ .

\sum_{i = 0}^{2 n} 2^{i} = 2^{2 n + 1} - 1 = O (4^{n})

$\sum_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$

Rozważmy algorytm rekurencyjny, który przemierza drzewo, które opisałeś, ale zlicza jedynki i zera na swojej drodze, tzn. Będzie on przechodził tylko przez dobrą część drzewa.
Ale ile jest takich ciągów binarnych z i ? Wybieramy 1 dla naszych łańcuchów długości $n$ $n$ $n$ i używamy wzoru Stirlinga w kroku 2: $2n$

(\binom{2 n}{n}) = \frac{(2 n)!}{(n!)^{2}} = \frac{4^{n}}{\sqrt{π n}} (1 + O (1 / n))

${2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$

EDYCJA
Dzięki komentarzom Petera Shora możemy również przeanalizować liczbę kroków wymaganych przez drugi algorytm, który zlicza jedynki i zera. Cytuję jego komentarz od dołu:

Chcemy znaleźć wszystkie sekwencje binarne o dokładnie 0 i 1. Przechodzimy przez drzewo binarne, w którym każdy węzeł jest sekwencją co najwyżej 0 i 1. Nie musimy odwiedzać żadnego węzła z więcej niż 0 lub więcej niż $n$ $n$ $2n$ $n$ $n$ 1. ile węzłów musimy odwiedzić? Istnieją ciągi z0 i1. Podsumowując to dla wszystkichdaje ${i+j \choose i}$ $i$ $j$ $i,j \leq n$ . Teraz musimy odwiedzić każdy z tych węzłów przy stałym średnim koszcie na węzeł. Możemy to zrobić, odwiedzając najpierw każde lewe dziecko, a każde prawe drugie dziecko. $\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$

Korzystając ponownie ze wzoru Stirlinga, otrzymujemy jako czas działania nowego algorytmu.

(\binom{2 n + 2}{n + 1}) - 1 = 4^{n + 1} \frac{1}{\sqrt{n + 1}} (1 + O (1 / n)) - 1 = O (\frac{4^{n}}{\sqrt{n}})

${2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}})$

— tranisstor
źródło

Musisz być bardziej ostrożny. Przypuszczalnie po wygenerowaniu każdego ciągu przetwarzamy go w czasie

. Przetwarzanie wszystkich zbalansowanych ciągów zajmuje więc czas

Ω (n)

$\Omega(n)$

. Jeśli zoptymalizowanym algorytmem „głupiego” generowania jest rzeczywiście

, wówczas przejście na inteligentniejszy algorytm nie jest niczym więcej niż szansa na błędy.

Ω (4^{n} \sqrt{n})

$\Omega(4^n \sqrt{n})$

O (4^{n})

$O(4^n)$

— Yuval Filmus

@Yuval Filmus: Co dokładnie oznacza „przetwarzanie łańcuchów”? Jeśli masz na myśli czas spędzony na wyjściu, który z pewnością wynosi

, musisz wziąć pod uwagę ten czynnik również w czasie działania algorytmu „głupiego”, którym jest

Θ (n)

$\Theta(n)$

O (4^{n} n)

$O(4^n n)$

— tranisstor

Chodzi mi o to, że jeśli martwisz się różnicą między

4^{n}

$4^n$

, następnie musisz podać poprawne czasy działania;

nie wystarczy, aby ujawnić jakąkolwiek potencjalną różnicę między dwoma algorytmami. Ponadto musisz uważnie analizować proponowany nowy algorytm, aby zobaczyć, że te „nieistotne” małe czynniki nie powodują, że jest on wolniejszy niż algorytm trywialny.

4^{n} / \sqrt{n}

$4^n/\sqrt{n}$

\tilde{O} (4^{n})

$\tilde{O}(4^n)$

— Yuval Filmus

Jak zbudować „dobrą część” drzewa bez konieczności uwzględniania „złych części”? Musisz uwzględnić wszystkie węzły drzewa, które nie mają więcej niż

lewych dzieci lub

prawych dzieci na ścieżce od katalogu głównego do nich. To działa, ale potrzebujesz dodatkowego argumentu, aby pokazać, że działa. W szczególności musisz użyć wzoru

n

$n$

n

$n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n} (\binom{i + j}{i}) = (\binom{2 n + 2}{n + 1}) - 1

$\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} -1$

— Peter Shor

n

$n$

n

$n$

2 n

$2n$

n

$n$

n

$n$

(\binom{i + j}{i})

$i+j \choose i$

i

$i$

j

$j$

i, j \leq n

$i,j \leq n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n} (\binom{i + j}{i}) = (\binom{2 n + 2}{n + 1}) - 1

$\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i}={2n+2 \choose n+1}-1$

Być może jestem gruby, ale pierwotne pytanie dotyczyło sposobu wygenerowania wszystkich „zbalansowanych” sekwencji binarnych o długości 2n, który byłby bardziej wydajny niż przemierzanie drzewa wszystkich sekwencji binarnych o długości 2n i generowanie tylko tych, które były zrównoważone. Po co więc w ogóle korzystać z drzewa?

Oto pseudokod algorytmu rekurencyjnego, który generuje wszystkie takie sekwencje (słowo kluczowe „wydajność” wysyła sekwencję na wyjście):

function all-balanced(n) {
  all-specified( "", n, n );
};

function all-specified( currentString, zeroes, ones ) {

  if (zeroes == 0) {
    for i = 0 to ones {
      currentString += "1";
    };
    yield currentString;
    return;
  };

  if (ones == 0) {
    for i = 0 to zeroes {
      currentString += "0";
    };
    yield currentString;
    return;
  };

  all-specified( currentString+"0", zeroes-1, ones );
  all-specified( currentString+"1", zeroes, ones-1 );
  return;
};

Jeśli coś nie rozumiem, powiedz mi, ale wydaje mi się, że chodzi o najbardziej skuteczną odpowiedź na postawiony problem, który nigdy nie określał użycia drzewa.

— afeldspar
źródło