Zablokowane X Przedmiotów, ile możliwości połączenia?

[Roki]

Mam problem, otóż załóżmy że mam ileś przedmiotów. Ta liczba to X. Jak zrobić, aby program wyliczał na ile możliwości mogę połączyć te rzeczy, których jest X? Na przykład X=3, czyli mam sobie np. x1 = A, x2 = B, a x3 = C i teraz, mogę to tak połączyć:

 

ABC

AB

AC

BC

 

To są wszystkie możliwe połączenia dla X = 3, a jeśli X=5, to? Albo X = 98126? Jak to wyliczyć?

[Lunatyk]

#include <iostream>
#include <conio.h>

int main(void)
{
    int x;
    int ilosc = 0;
    std::cin >> x;
    int * t = new int[x];
    for(int n = 0; n < x; n++)
        t[n] = n;
    for(int i = 0; i < x; i++)
        for(int j = i+1; j < x; j++)
        {
            ilosc++;
            std::cout << t[i] << " i " << t[j] << std::endl;
        }
    std::cout << "Ilosc kombinacji: " << ilosc;
    delete [] t;
    getch();
    return 0;
}

[Platyna]

Kombinatoryka się kłania.

Możliwych kombinacji jest 2^X. Bo każdy przedmiot możesz wziąć, albo nie wziąć do zbioru.

 

EDIT:

A Pan wyżej coś nie bardzo, bo z tego co widzę to tylko bierze kombinacje dwuelementowe.

[Roki]

^ = do potęgi?

W takim razie: 2^3 = 8, a nie 4 jak powinno wyjść :P

mannor -> Tyle że to liczy tylko kombinacje 2 połączeń ;/ Na razie idę do szkoły jeszcze, wrócę to coś pokminie, jak ktoś odpisze to ofc zobaczę :)

[Platyna]

Tak to jest do potęgi. Bo to ci jeszcze liczy możliwości wzięcia 1 elementu oraz żadnego czyli dodatkowe 4 kombinacje.

Jak chcesz takie pominąć to po prostu od wyniku odejmij X+1.

 

EDIT:

No i oczywiście nie zapominaj, że wystarczy X>64, a wynik już ci przekroczy zakres unsigned long longa. Będziesz potrzebował napisać własną arytmetykę.

[Roki]

Dzięki :) Aż tak wielkich liczb jak X>64 chyba nie potrzebuje :)

Temat zamykam :P