Witam serdecznie.
Mam taki problem: potrzebuję wypisać wszystkie k-liczbowe kombinacje z n-elementowego zbioru liczb naturalnych. Ma ktoś pomysł? Na forum znalazłem podobny post, lecz nie dokońca jest to to czego szukam. Pozdrawiam.
Ja bym do tego użył funkcji rekurencyjnej:
void fun (int ile_juz_liczb_jest,int ile_liczb_juz_wykorzystanych)
{
...
otrzymana+=licby_wszystkie[++ile_liczb_juz_wykorzystanych]
...
if (ile_juz_liczb_jest==ile_ma_byc) {cout << otrzymana; return;}
else fun(...);
...
}
A możesz objaśnić zmienne ile_juz_liczb_jest i ile_liczb_juz_wykorzystanych?
tworzysz zmienną globalną, np jak w przykładzie o nazwie otrzymana, w której będziesz przechowywał twoją liczbę, którą masz otrzymać jako gotową kombinację. W main funkcję wywołasz z parametrami (0,0). W pierwszym argumencie (ile_juz_liczb_jest) rekurencja będzie podawała, ile liczb zawiera już zmienna "otrzymana". Kiedy liczba ta będzie równa k (patrz -> twój pierwszy post), to liczba zostanie wypisana. Drugi argument (ile_liczb_juz_wykorzystanych), informuje, ile liczb zostało wykorzystanych, z tego n-elementowego zbioru na danym miejscu.
Należy się jeszcze zastanowić, jakiego typu będzie zmienna "otrzymana". Najlepiej chyba tablica "int otrzymana [k]" się do tego nadaje. Tylko wtedy przypisywanie będzie wyglądałe trochę inaczej niż podane przeze mnie powyżej, czyli:
otrzymana[ile_juz_liczb_jest]=licby_wszystkie[++ile_liczb_juz_wykorzystanych];
Wiem, że to może trochę zawile brzmi, ale tak to jest, jak się samemu nie myśli, tylko prosi o to kogoś innego. A gotowego rozwiązania przecież Ci nie poadm!
ogólnie idea jest taka: na danym poziomie rekurencji albo bierzesz liczbę na aktualnym indeksie (indeksem jest tutaj poziom rekurencji) i wywołujesz funkcję rekurencyjnie dla ilości elementów o jeden mniejszej, albo nie bierzesz liczby i wywołujesz funkcję dla takiej samej liczby elementów. jeśli zapełniłeś cały zbiór (tzn. wybrałeś k elementów) to je wypisujesz i wychodzisz.
powiedzmy, że masz stos liczb (to będzie na naszą kombinację k elementową)
mamy:
rekursja(int poziom, int pozostało)
{
// za mało elementów wybraliśmy
if (poziom > n)
return;
// ok. wybraliśmy k elementów - wypisujemy
if (pozostało == 0)
{
wypisz(stos);
return;
}
// sytuacja 1: bierzemy liczbę na akutalnym indeksie
stos.push(zbiór[poziom]);
rekursja(poziom + 1, pozostało - 1);
stos.pop(); // powróć do poprzedniego stanu
// sytuacja 2: nie bierzemy liczby na aktualnym indeksie
rekursja(poziom + 1, pozostało);
}
w mainie wywołujemy jako:
rekursja(0, k);
JaskMar, _donkey7: wasze pomysły nie zadziałają bez pętli.
rekurencja: Dla każdego elementu 'i' rekurencji, za którym stoi przynajmniej tyle elementów ile brakuje do pełnej kombinacji, wykonuj rekurencję dla elementów stojących za 'i':
#include <iostream>
#include <vector>
using namespace std;
class kombinacje
{
private:
double *zbior;
int n;
vector<int> stos;
void rekursja(int poziom, int pozostalo)
{
//jesli kombinacja jest pelna, trzeba ja wypisac czy tam cos innego zrobic
if (pozostalo == 0)
{
for(int i = 0; i < stos.size(); i++) cout << zbior[stos[i]] << ' ';
cout << endl;
return;
}
//w nastepnej rekurencji zostanie o 1 mniej elementow do pelnej kombinacji
pozostalo--;
//bierzemy elementy, dopóki za nimi stoi przynajmniej 'pozostalo' elementów
while(n - poziom > pozostalo)
{
//bierzemy element
stos.push_back(poziom);
//wywolujemy rekurencje dla elementów stojących dalej
poziom++;
rekursja(poziom, pozostalo);
//zostawiamy element, aby wziac nastepny
stos.pop_back();
}
}
public:
kombinacje(double _zbior[], int _n, int k)
: zbior(_zbior), n(_n) { rekursja(0, k); }
};
double tab[] = { 1., 2., 3., 4., 5. };
int main(int argc, char* argv[])
{
kombinacje(tab, sizeof(tab) / sizeof(double), 3);
cin.get(); return 0;
}
Witam ponownie :-)
Bardzo dziękuję koledze @adf88, bo jego rozwiązanie jak najbardziej działa :-)
Obecnie postaram się to zmodyfikować, żeby wynik był zapisany do kolejnych wierszy w tablicy dwuwymiarowej, ale gdybym sobie nie poradził, to pewnie się tutaj zgłoszę :-)
Pozdrawiam i wesołych świąt!
A nie jest przypadkiem w STLu jakaś funkcja od kombinacji?
A jest? Ja szukałem i nie znalazłem, być może byłoby mniej pracy, ale już nieważne :)
działa :-)
Pozdrawiam.
Na szybko znalazłem coś takiego: http://www.sgi.com/tech/stl/next_permutation.html Nie czytałem dokładnie tematu i nie wiem, czy to o to chodzi, ale w STLu jest wszystko :)
Pozdrawiam