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

Odpowiedz Nowy wątek
2016-04-10 17:00

Rejestracja: 4 lata temu

Ostatnio: 3 lata temu

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

Pozostało 580 znaków

kq
2016-04-10 17:03
kq
Moderator C/C++

Rejestracja: 6 lat temu

Ostatnio: 20 godzin temu

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.


Pozostało 580 znaków

2016-04-10 17:06

Rejestracja: 4 lata temu

Ostatnio: 3 lata temu

0

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

To masz szczęście. std::set jest szablonem, a nie klasą :) - kq 2016-04-10 17:12
Jak już wspominałem nie jestem bardzo biegły w programowaniu, a o szablonach nie mialem jeszcze okazji sie uczyć :/ - pietras9 2016-04-10 17:16

Pozostało 580 znaków

2016-04-10 17:10

Rejestracja: 8 lat temu

Ostatnio: 4 dni temu

0

dlaczego raczej zabronione?

Pozostało 580 znaków

2016-04-10 17:13

Rejestracja: 4 lata temu

Ostatnio: 3 lata temu

0

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

Pozostało 580 znaków

2016-04-10 17:17

Rejestracja: 7 lat temu

Ostatnio: 58 minut temu

Lokalizacja: Kraków

1

http://algorytmykombinatoryczne.w.interiowo.pl/algorytm1.html


Wydaje mi się że ten algorytm nie zadziałą, tam wypisane będzie np 123 i 132, a w kombinacjach bez powtorzeń 123 i 132 są tożsame. - pietras9 2016-04-10 17:24

Pozostało 580 znaków

2016-04-10 19:47

Rejestracja: 14 lat temu

Ostatnio: 3 dni temu

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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
tylko ze, są tu powtórzenia np 2 1 2 5 i 2 1 2 6 (powtarzaja sie dwojki) - pietras9 2016-04-10 20:02

Pozostało 580 znaków

Odpowiedz

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