Generowanie wszystkich podzbiorów

Jeśli chcemy zastosować pewną operację do każdego podzbioru danego zbioru, wtedy musimy w odpowiedni sposób wygenerować te podzbiory. Nie ma możliwości, aby wykonać to w czasie wielomianowym, gdyż liczba podzbiorów zbioru N-elementowego wynosi 2^N. (Wliczamy tu także podzbiór pusty i podzbiór zawierający wszystkie elementy danego zbioru.)

Oznaczmy nasz zbiór przez A, a jego liczbę elementów przez N. Elementy zbioru A ponumerujemy i oznaczymy przez A_i, i = 0, 1, …, N-1. Każdy jego podzbiór można jednoznacznie scharakteryzować ciągiem N bitów: jeśli bit na pozycji k-tej jest ustawiony, wtedy k-ty element zbioru A należy do tego podzbioru. Zatem każdy podzbiór posiada unikalną sygnaturę w postaci liczby całkowitej z przedziału 〈0; 2^N-1〉:

Przykład dla N = 7
sygnatura: (0101001)₂ = (9)₁₀

Do podzbioru należą elementy: A₀, A₃, A₅

Algorytm, który wybiera elementy zbioru A w oparciu o sygnaturę S ma postać:

subset(S)
   list = {Ø}
   mask = 1
   for i=0 to N-1 do
      if mask & S > 0
         put(list, A[i])
      mask = mask << 1
   return list

Operatory & oraz << to operatory bitowe (jak w C++), zaś funkcja put powoduje dołączenie kolejnego elementu do listy.

Wszystkie podzbiory generujemy (i ewentualnie przetwarzamy) przez wykonanie pętli:

M = (1<<N)-1
for S=0 to M do
   process(subset(S))

Na przykład dla N=7 i zbioru A={1,2,3,4,5,6,7} otrzymamy kolejno następujące podzbiory:

{Ø}
1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4

5
1 5
2 5
1 2 5
3 5
1 3 5
2 3 5
1 2 3 5
4 5
1 4 5
2 4 5
1 2 4 5
3 4 5
1 3 4 5
2 3 4 5
1 2 3 4 5

6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6
4 6
1 4 6
2 4 6
1 2 4 6
3 4 6
1 3 4 6
2 3 4 6
1 2 3 4 6

5 6
1 5 6
2 5 6
1 2 5 6
3 5 6
1 3 5 6
2 3 5 6
1 2 3 5 6
4 5 6
1 4 5 6
2 4 5 6
1 2 4 5 6
3 4 5 6
1 3 4 5 6
2 3 4 5 6
1 2 3 4 5 6

7
1 7
2 7
1 2 7
3 7
1 3 7
2 3 7
1 2 3 7
4 7
1 4 7
2 4 7
1 2 4 7
3 4 7
1 3 4 7
2 3 4 7
1 2 3 4 7

5 7
1 5 7
2 5 7
1 2 5 7
3 5 7
1 3 5 7
2 3 5 7
1 2 3 5 7
4 5 7
1 4 5 7
2 4 5 7
1 2 4 5 7
3 4 5 7
1 3 4 5 7
2 3 4 5 7
1 2 3 4 5 7

6 7
1 6 7
2 6 7
1 2 6 7
3 6 7
1 3 6 7
2 3 6 7
1 2 3 6 7
4 6 7
1 4 6 7
2 4 6 7
1 2 4 6 7
3 4 6 7
1 3 4 6 7
2 3 4 6 7
1 2 3 4 6 7

5 6 7
1 5 6 7
2 5 6 7
1 2 5 6 7
3 5 6 7
1 3 5 6 7
2 3 5 6 7
1 2 3 5 6 7
4 5 6 7
1 4 5 6 7
2 4 5 6 7
1 2 4 5 6 7
3 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 4 5 6 7

Powrót do Algorytmy wykładnicze

Algorytmika