Bijekcja między ciągami binarnymi długości n, a podzbiorami

vishera · Post autor: **vishera** » 18 mar 2015, o 20:45

Cześć! Mam problem z zadaniem, którego treść najlepiej przytoczę na początku, żeby każdy wiedział o czym dokładnie mowa:

"Wygeneruj wszystkie podzbiory zbioru {1,2,...,n} wykorzystując bijekcję między ciągami binarnymi długości n, a tymi podzbiorami."

Na przykładzie n = 3:
Rozumiem, że zbiór w tym przypadku wygląda następująco: {1,2,3} a przykładowy ciąg binarny może być 101. Czy w takiej sytuacji "jedynki" traktuję jako miejsca, które może zająć dokładnie 1 element ze zbioru? Czy te elementy mogą się powtarzać?

Proszę o nakierowanie na odpowiednią drogę, bo temat ten jest dla mnie jak kula przywiązana do nogi.
Z góry dzięki!

mostostalek · Post autor: **mostostalek** » 18 mar 2015, o 21:14

Przyporządkowujesz każdą liczbę, ze zbioru miejscu w ciągu binarnym o tym samym indeksie.. Jedynka w ciągu binarnym będzie oznaczała, że liczba przyporządkowana temu indeksowi należy do podzbioru, 0 - jest odwrotnie..

W ten sposób ciąg o samych zerach będzie odpowiadał zbiorowi pustemu, ciąg o samych jedynkach całemu zbiorowi, itd.

vishera · Post autor: **vishera** » 19 mar 2015, o 10:39

Dzięki za szybką odpowiedź, wszystko mi wyjaśniłeś