Filip Klar web developer blog

Zbiór potęgowy to według definicji zbiór wszystkich podzbiorów danego zbioru. Brzmi trochę skomplikowanie, ale po krótkim zastanowieniu wcale takie nie jest. W tym poście przedstawię właśnie sposób na wyszukanie wszystkich podzbiorów za pomocą języka programowania (w moim przykładzie będzie to oczywiście PHP). Wydaje się, że wypisanie tych zbiorów należy do prostych zadań. Zajęło mi jednak trochę czasu wykombinowanie, w jaki sposób podejść do tego tematu. Kiedy pierwszy raz brałem się za to, w internecie nie znalazłem nic podobnego. Ostatecznie udało się, i to nawet prościej niż się spodziewałem, choć być może istnieje inna metoda na uzyskanie tego efektu.

Podstawy

Na początek trochę teorii. Każdy zbiór potęgowy składa się ze zbioru pustego oraz wszystkich niepowtarzających się zbiorów złożonych ze wszystkich elementów. Aby przybliżyć to o co mi chodzi, posłużę się przykładem zbioru składającego się wyłącznie z liczb 1 i 2. Tak więc wszystkie podzbiory zbioru A = {1, 2} to:

• ∅
• {1}
• {2}
• {1, 2}

Jak widać, są one cztery. Wzór na ich liczbę to:

|P(A)| = 2^|A|

Dla nas jest to bardzo ważna informacja, gdyż liczba podzbiorów będzie użyta do sterowania pętlą. W moim przypadku jako zbiory będą służyły tablice z danymi. Jest to bardzo wygodne i praktyczne.

Jak to działa?

Nasze działania będą wyglądały następująco: dopóki liczba wyszukanych podzbiorów nie będzie równa 2^|A|, będziemy przeglądali po kolei wszystkie dotąd znalezione zbiory, a podczas tej czynności sprawdzali elementy głównego zbioru.

Po co to? Jeśli napotkamy na element, którego nie ma jeszcze w danym podzbiorze, utworzymy nowy podzbiór – taki sam, lecz wzbogacony o właśnie ten element.

No dobrze, ale od czego zacząć, skoro nie mamy jeszcze żadnego podzbioru? A właśnie, że mamy, jak wcześniej pisałem, w każdym zbiorze potęgowym znajduje się zbiór pusty. I od niego zawsze będziemy zaczynać.

Przykład dla {1, 2}

Najlepiej pokaże to oczywiście przykład. Weźmiemy więc pod uwagę znowu zbiór {1, 2}. A więc zaczynając mamy już:

• ∅

Bierzemy więc pierwszą liczbę, jedynkę, i dopisujemy do już wypisanych zbiorów (a właściwie zbioru):

• {1}

Co daje nam razem:

• ∅
• {1}

A teraz to samo z dwójką:

• {2}
• {1, 2}

Po zsumowaniu:

• ∅
• {1}
• {2}
• {1, 2}

Mamy już cztery podzbiory, więc to koniec algorytmu. Jak widać, są one te same, jak w pierwszym podanym przeze mnie przykładzie.

Podobnie dla {1, 2, 3}

Aby otrzymać zbiór potęgowy zbioru {1, 2, 3} wystarczy do otrzymanego przed momentem P({1, 2}) dopisać trójkę:

• {3}
• {1, 3}
• {2, 3}
• {1, 2, 3}

i połączyć oraz posortować:

• ∅
• {1}
• {2}
• {3}
• {1, 2}
• {1, 3}
• {2, 3}
• {1, 2, 3}

Myślę, że teraz jest to już jasne. Może nie do końca dobrze to opisałem, ale wystarczy przyjrzeć się powyższym przykładom, żeby zrozumieć zasadę działania algorytmu. Pokaże więc teraz ostatni już przykład, tym razem oparty na literach A, B, C oraz D.

Zbiór złożony z liter

Wiadomo już, że startujemy ze zbiorem pustym:

• ∅

Dopisujemy do niego A:

• {A}

Razem:

• ∅
• {A}

Drugie dopisanie – B:

• {B}
• {A, B}

Razem:

• ∅
• {A}
• {B}
• {A, B}

Trzecie dopisanie – C:

• {C}
• {A, C}
• {B, C}
• {A, B, C}

Razem:

• ∅
• {A}
• {B}
• {A, B}
• {C}
• {A, C}
• {B, C}
• {A, B, C}

Czwarte dopisanie – D:

• {D}
• {A, D}
• {B, D}
• {A, B, D}
• {C, D}
• {A, C, D}
• {B, C, D}
• {A, B, C, D}

Zbiór końcowy:

• ∅
• {A}
• {B}
• {A, B}
• {C}
• {A, C}
• {B, C}
• {A, B, C}
• {D}
• {A, D}
• {B, D}
• {A, B, D}
• {C, D}
• {A, C, D}
• {B, C, D}
• {A, B, C, D}

Wypadałoby to jeszcze posortować, ale wybaczcie, nie chce mi się tego ręcznie robić. Poza tym teraz dużo lepiej widać nasze działania.

Implementacja w PHP

Teraz, gdy już wiecie, jak teoretycznie to zrobić, przedstawiam gotową funkcję PHP, która zwraca zbiór potęgowy wybranego zbioru:

function zbiorPotegowy($array) {

$result[] = array();

while(count($result) < pow(2, count($array))) { foreach($result as $set) { foreach($array as $number) { $temp = $set; if($temp[count($temp)-1] < $number) { $temp[] = $number; if(!in_array($temp, $result)) $result[] = $temp; } } } } sort($result); return $result; } [/php] Oczywiście tak jak wspominałem, jako zbiory potraktowałem tu tablice. Jako argument funkcji zbiorPotegowy() należy podać dowolną tablicę, a jako rezultat otrzymamy tablicę tablic podobną do tego, co przedstawiłem na powyższych przykładach.