Witam, mam za zadanie napisanie programu wypisującego wszystkie n-elementowe kombinacje bez powtorzeń cyfr naturalnych czyli np 3-elementowe kombinacje zbioru 4 elementowego to będzie 0 1 2 3, 0 1 2 4, 0 1 3 4 itd, ma to być zrobione rekurencyjnie, ale jako że jestem dosyc poczatkujacy w programowaniu nie wiem za bardzo jak sie za to zabrac. Z góry dziękuje za pomoc :)
Generowanie kombinacji m-elementowych zbioru n-elementowego bez powtórzeń
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Szczecin
0
Kombinacje, które wypisałeś są 4-elementowe.
Jeśli rekurencyjnie to najprościej pewnie będzie użyć do tego klasy std::set i zwracać jakąś listę setów, ale to dość mało wydajne rozwiązanie.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 6
0
Racja, mój błąd ,a jesli chodzi a użycie klasy std::set, to raczej mamy to zabronione (zadanie na studiach).
- Rejestracja: dni
- Ostatnio: dni
- Postów: 6
0
Tak już mamy, nie możemy używać wiekszości rzeczy ułatwiających pisanie programów.
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Kraków
- Postów: 1055
- Rejestracja: dni
- Ostatnio: dni
0
#include <iostream>
#include <vector>
using namespace std;
void short_permutation(vector<int> &tb,size_t count)
{
vector<size_t> idx(count);
for(size_t pos=0;pos<count;)
{
vector<size_t> tmp(idx);
for(size_t i=1;i<tmp.size();++i) for(size_t k=0;k<i;++k) tmp[i]+=(tmp[k]<=tmp[i]);
for(size_t i=0;i<tmp.size();++i) cout<<(" "+!i)<<tb[tmp[i]];
cout<<endl;
for(pos=count-1;(pos<count)&&((++idx[pos])>=tb.size()-pos);--pos) idx[pos]=0;
}
}
int main()
{
vector<int> tb{1,2,3,4,5,6};
short_permutation(tb,4);
return 0;
}