Kombinacje bez powtórzeń - jak znaleźć wszystkie?

Witam,

przeglądałem wątki na ten temat i nie znalazłem odpowiedzi bo generalnie ludzie nie rozróżniają czym jest kombinacja, wariacja, permutacja itd. Natomiast to co znalazłem dotyczyło szczegółowych sytuacji dlatego chciałbym zadać pytanie.

Jak skonstruować algorytm, który zapisze wszystkie możliwe kombinacje bez powtórzeń ze zbioru n-elementowego w dowolnych strukturach. (np. tablicach)?

Ewentualnie mogą to być wszystkie k-elementowe kombinacje, bo potem już nie ma problemu w skompletowniu podzbiorów dla każdego k.

Muszę napisać taki algorytm w c++ lub perlu.

Az trzeba bylo 1 funkcje znalezc! Coz za wysilek.

int main() {
	vector<int> arr = {1,2,3};
	do {
		copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
		cout << "\n";
	} while(next_permutation(arr.begin(), arr.end()));
	return 0;
}

mari6274 napisał(a):

przeglądałem wątki na ten temat i nie znalazłem odpowiedzi bo generalnie ludzie nie rozróżniają czym jest kombinacja, wariacja, permutacja itd.

No brawo. To są permutacje.

Nie, nie sa. Permutacja to funkcja. To sa wszystkie mozliwe przeksztalcenia zbioru, dzieki temu nie trzeba sie w nic bawic, tylko wrzucac pokolei podzbiory do set'a.

Ten kod wypisuje wszystkie permutacje zbioru. Ja nie chce permutacji. Ja chce kombinacje.

Może to ci pomoże:

mari6274 napisał(a):

Ewentualnie mogą to być wszystkie k-elementowe kombinacje, bo potem już nie ma problemu w skompletowniu podzbiorów dla każdego k.

Jeżeli nie to podaj swoją definicje tego co szukasz, ponieważ @n0name_l, ja i prawdopodobnie inni znamy wyłącznie tą matematyczną definicje, niestety.

To znacie złą definicję. Permutacja to ciąg, a kombinacja to zbiór. Oznacza to, że kombinacje (1,2,3) i (2,3,1) to ta sama kombinacja natomiast permutacje (1,2,3) i (2,3,1) to 2 różne permutacje.

Przykład:
Mamy zbiór {1,2,3,4}
Wszystkie permutacje wyliczone przez program:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Kombinacje tego zbioru o przykładowo 3 elementach to: {1,2,3}, {1,3,4}, {1,2,4} i {2,3,4}

Olaboga.

dzieki temu nie trzeba sie w nic bawic, tylko wrzucac pokolei podzbiory do set'a.

mari6274 napisał(a):

To znacie złą definicję. Permutacja to ciąg, a kombinacja to zbiór. Oznacza to, że kombinacje (1,2,3) i (2,3,1) to ta sama kombinacja natomiast permutacje (1,2,3) i (2,3,1) to 2 różne permutacje.

Bo my znamy pojęcie "sprowadzania problemu do innej formy".

No to nic dziwnego że nie znalazłeś, założę się że algorytmu na obliczenie 2+2 też nie znajdziesz:

#include <iostream>
#include <cstring>
using namespace std;

int main()
  {
   char str[]="1234";
   unsigned len=strlen(str);
   for(unsigned i=(1<<len);--i;cout<<endl) for(unsigned k=0;k<len;++k) if((i>>k)&1) cout<<str[k];
   return 0;
  }