Kombinacja bez powtórzeń

Odpowiedz Nowy wątek
mythbusters
2007-12-12 16:47
mythbusters
0

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.

Pozostało 580 znaków

2007-12-12 17:01

Rejestracja: 13 lat temu

Ostatnio: 2 miesiące temu

0

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(...);
...
}

#include<hacking.h>
char *a=schakuj_pentagon("pobierz_baze_danych"); //<-odkrywczy kod;

Pozostało 580 znaków

mythbusters
2007-12-12 17:20
mythbusters
0

A możesz objaśnić zmienne ile_juz_liczb_jest i ile_liczb_juz_wykorzystanych?

Pozostało 580 znaków

2007-12-12 17:43

Rejestracja: 13 lat temu

Ostatnio: 2 miesiące temu

0

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 przezemnie 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!


#include<hacking.h>
char *a=schakuj_pentagon("pobierz_baze_danych"); //<-odkrywczy kod;

Pozostało 580 znaków

_donkey7
2007-12-12 22:05
_donkey7
0

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

Pozostało 580 znaków

2007-12-13 10:44

Rejestracja: 16 lat temu

Ostatnio: 6 lat temu

0

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

Pozostało 580 znaków

mythbusters
2007-12-13 18:41
mythbusters
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!

Pozostało 580 znaków

2007-12-13 22:20

Rejestracja: 12 lat temu

Ostatnio: 11 minut temu

0

A nie jest przypadkiem w STLu jakaś funkcja od kombinacji?

Pozostało 580 znaków

mythbusters
2007-12-15 16:44
mythbusters
0

A jest? Ja szukałem i nie znalazłem, być może byłoby mniej pracy, ale już nieważne :)
działa :-)
Pozdrawiam.

Pozostało 580 znaków

2007-12-16 11:09

Rejestracja: 12 lat temu

Ostatnio: 11 minut temu

0

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

Pozostało 580 znaków

Odpowiedz

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