Generowanie kombinacji m-elementowych zbioru n-elementowego bez powtórzeń

0

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 :)

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.

0

Racja, mój błąd ,a jesli chodzi a użycie klasy std::set, to raczej mamy to zabronione (zadanie na studiach).

0

dlaczego **raczej **zabronione?

0

Tak już mamy, nie możemy używać wiekszości rzeczy ułatwiających pisanie programów.

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;   
  }

1 użytkowników online, w tym zalogowanych: 0, gości: 1