Witam
Mam taki problem, który mnie chyba przerasta. Otóż mam pewien zbiór liczb naturalnych A. W tym oto zbiorze interesuje mnie tylko ile liczb on zawiera (N), gdyż wtedy do zbioru A należą liczby {1,2,3..N}. Teraz należy go rozłożyć na wszystkie możliwe podzbiory w których zawiera się K liczb, przy czym K należy do naturalnych i spełnia nierówność 0 < K < N.
Dla przykładu zbiór A w którym zawiera się 6 liczb będzie wyglądał następująco:
A:{1,2,3,4,5,6}
Rozłóżmy go na wszystkie możliwe podzbiory w których zawierać się będą 2 liczby:
1,2
1,3
1,4
1,5
1,6
2,3
2,4
2,5
2,6
3,4
3,5
3,6
4,5
4,6
5,6
Widać więc, że tych podzbiorów może być 15. Wszystko ładnie fajnie tylko teraz muszę napisać funkcję, która policzy te podzbiory.
Jeżeli jest już gotowy algorytm na to i ktoś go zna to bardzo proszę niech go poda, jeżeli nie to proszę o dalszą uwagę.
Z tego co wymyśliłem do tej pory to to, że dla dwóch liczb w podzbiorze ich ilość będzie wynosiła:
N-1 + N-2 + .. + N-(N-1)
Wiadomo, że dla podzbiorów zawierających jedną liczbę ich ilość będzie wynosiła N.
Pytanie teraz jak policzyć ilość podzbiorów zawierających więcej niż dwie liczby? :|
(N-1)-1+(N-1)-2 + ... +(N-1)-[(N-1)-1]+(N-2)-1+(N-2)-2+ ... +(N-2)-[(N-2)-1] ...
Tutaj mój mózg wywala segmentation fault...
Próbowałem jakoś rekurencyjnie z tym ruszyć, ale póki co nic z tego.
Mam nadzieje, że dość jasno określiłem problem, proszę więc o pomoc.