Kombination ohne Zurücklegen - Iterativ?
-
Ich suche eine Möglichkeit um bei einer bestimmten Anzahl von Zahlenwerten, für diese bezüglich einer limitierte Anzahl von Plätzen, alle Anordnungsmöglichkeiten zu berechnen. Wobei die Anordnungsreihenfolge egal ist.
Als Beispiel was ich meine: Die Zahlen 1-6 sind auf 4 Plätze zu verteilen.
Für diese sollte es folgende 15 Anordnungen geben:1234,1235,1236,1245,1246,1256,1345,1346,1356,1456,2345,2346,2356,2456,3456
Es gibt also keine Zahl doppelt und zwischen 12 sowie 21 wird nicht unterschieden.Ich habe gesehen das es in der STL die next_permutation Funktion gibt. Was jedoch leider nur auf das "geschwister" Problem ausgerichtet ist in welchem Plätze und Zahlenanzahl gleichgroß sind.
Und irgendwie finde ich keine Iterative Lösung die halbwegs überschaubar wäre und auch noch alle geforderten Kombinationen effizient durchläuft.
-
Hast du denn schon eine rekursive Lösung? Wenn ja, dann ist es auf dieser Basis meist nicht sooo schwer, es zu iteritativieren.
-
Hallo,
hier mal ein ganz primitiver Ansatz, der dich vielleicht zu optimialeren Lösungen inspiriert:void print_n_choose_k(unsigned n, unsigned k) { if (n < k) return; std::vector<unsigned> st; const unsigned end = n+1; unsigned next = 1; unsigned nr = 0; for (;;) { if (st.size() == k) { std::cout << ++nr << ": "; std::copy(st.begin(), st.end(), std::ostream_iterator<unsigned>(std::cout, " ")); std::cout << "\n"; next = end; } while (next == end || (st.size()+(end-next)) < k) { if (st.empty()) return; next = st.back()+1; st.pop_back(); } st.push_back(next++); } }
-
Badestrand schrieb:
Hast du denn schon eine rekursive Lösung? Wenn ja, dann ist es auf dieser Basis meist nicht sooo schwer, es zu iteritativieren.
Also von recursiv auf iterativ und umgekehrt zu arbeiten fällt mir oft ziemlich schwierig.
#include<iostream> using namespace std; void recCombination(int elements[],int places[],int firstElement, int secondElement,int sumPlaces,int loops) { int localLoops=loops; int localfirstElement=firstElement; //---Ausgabe if(secondElement>=sumPlaces) { for(int i=0; i<sumPlaces; i++){ cout<<places[i]; } cout<<endl; return; } //--- for(int i=0;i<=loops;i++) { places[secondElement]=elements[firstElement+i]; localfirstElement++; recCombination(elements,places,localfirstElement,secondElement+1,sumPlaces,localLoops); localLoops--; } } int main() { int sumElements=6; int sumPlaces=4; int elements[]={1,2,3,4,5,6}; int places[sumPlaces]; recCombination(elements,places,0,0,sumPlaces,sumElements-sumPlaces); return 0; }
-
So, ich hab mal nen paar Sachen verändert, um das Ganze ein wenig zu vereinfachen. Soll dazu dienen, dass du leichter auf die iterative Lösung kommst
"localfirstElement" brauchst du gar nicht, da es immer "firstElement+i+1" entspricht.
sumPlaces, elements und places hab ich oben drüber gepackt, weil die ja einfach immer nur durchgereicht werden.
localLoops brauchst du auch nicht mehr, wird nur in der Schleife verwendet und entspricht immer loops-iint elements[]={1,2,3,4,5,6}; const int sumPlaces = 4; int places[sumPlaces]; void recCombination(int firstElement, int secondElement,int loops) { //---Ausgabe if(secondElement>=sumPlaces) { for(int j=0; j<sumPlaces; j++) cout<<places[j]; cout<<endl; return; } for(int i=0;i<=loops;i++) { places[secondElement]=elements[firstElement+i]; recCombination(firstElement+i+1,secondElement+1,loops-i); } }Das lässt sich umwandeln in
void recCombination(int firstElement, int secondElement,int loops) { for ( int i=0; i<=loops; i++ ) { if(secondElement>=sumPlaces) { for(int i=0; i<sumPlaces; i++) cout<<places[i]; cout<<endl; return; } places[secondElement] = elements[firstElement+i]; recCombination(firstElement+i+1,secondElement+1,loops-i); } }Als nächstes musst du eine äußere Schleife finden, die dein Iterativ-Ding ummantelt. Um die Rekursionstiefe abzubilden, können wir eine Variable "depth" deklarieren, die bei einem Pseudo-Aufruf hochgezählt und bei einem Pseudo-return heruntergezählt wird.
Die Parameter-Variablen und die Zählervariable 'i' hab ich durch stacks ersetzt. Dabei wird bei jedem "Funktionsaufruf" ein neuer Initialsatz von Variablen auf den Stapel abgelegt. Wenn die quasi-for-Schleife fertig durchgelaufen ist oder das quasi-return ausgeführt werden soll, werden die obersten Elemente der Stacks weggepopt und die darunterliegenden werden frei:void recCombination(int firstElement, int secondElement,int loops) { // Die Stacks, welche die Variablen "der aktuellen Funktion" speichern stack<int> first; first.push( firstElement ); stack<int> second; second.push( secondElement ); stack<int> loop; loop.push( loops ); stack<int> i; i.push( 0 ); // Hier die äußere Schleife, die mit "1-Aufruf" anfängt und wartet, bis oft genug quasi-return't wurde int depth = 1; while ( depth > 0 ) { // Stellt die ehemalige for-Schleife dar. i wird am Schluss erhöht while ( i.top()<=loop.top() ) { if ( second.top() >= sumPlaces ) { for ( int j=0; j<sumPlaces; j++ ) cout << places[j]; cout << endl; // return wird umgewandelt in: first.pop(); second.pop(); loop.pop(); i.pop(); depth--; continue; } places[second.top()] = elements[first.top()+i.top()]; // Folgende Zeilen stellen den "Funktionsaufruf" dar: first.push( first.top()+i.top()+1 ); second.push( second.top()+1 ); loop.push( loop.top()-i.top() ); i.top()++; // i muss hier erhöht werden, gilt für die aktuelle for-Schleife depth++; i.push( 0 ); // für die nächste for-Schleife, die muss schließlich mit 0 anfangen } // Der Code kommt, wenn die for-Schleife durchgelaufen ist. first.pop(); second.pop(); loop.pop(); i.pop(); depth--; } }Das Ganze kannst du noch eine Ecke schöner und geordneter machen. Aber erstmal zählt, dass du hier eine iterative Lösung hast (na gut, Hume hat eine bessere, aber die hier geht von deiner aus :)). Hier kannst du nun nach Lust und Gedeihen rumpfuschen, bis es ordentlich aussieht.
-
HumeSikkins's Ansatz funktioniert soweit gut und nach den Sachen die ich getestet habe auch mit guter Geschwindigkeit.
An der umgestalltenen Version muß ich noch etwas herum probieren. Danke euch zwei für die Hilfe.
-
Gern geschehen
Aber wenn, dann nimm Humes Version, die ist sauber! Ich wollte nur demonstrieren, wie man mit etwas Aufwand die Rekursivität wegmachen kann.
-
Hallo,
hier noch eine STL-artige Variante, die ähnlich wie std::next_permutation arbeitet:// Reorders the elements in a range so that the original ordering is // replaced by the lexicographically next greater k-combination if it exists. // Note: k is specified using an iterator pointing to an element in the // range [first, end). template <class BI> bool next_combination(BI first, BI k, BI end) { if (first == k || k == end) return false; BI x = k; if (*(--x) < *k) { std::iter_swap(x, k); x = k; while (++k != end && *x < *k) { std::iter_swap(x, k); ++x; } return true; } // [first, k) : sorted by increasing value, e.g: [1, 2, 6, 8] // [kEnd, end): sorted by decreasing value, e.g: [7, 5, 4, 3] if (*k < *first) { // max combination - no element in [k, end) is greater than any element in [first, end). std::reverse(first, k); std::reverse(first, end); return false; } // find max x in [first, k), min y in [k, end), s.th. *x < *y while ( *k < *(--x) ) { ; } BI y = end; while ( *(--y) < *x ) { ; } // swap *x and *y and reorder the elements in between // s.th. they are again sorted by increasing value. std::iter_swap(x, y); if (k != y) { std::reverse(++x, k); std::reverse(x, y); } return true; }Den Algo habe ich mir gestern in der U-Bahn überlegt, ist also mit Sicherheit nicht der Weisheit letzter Schluss.
Anwendung:
int main() { int arr[6] = {1, 2, 3, 4, 5, 6}; int* end = arr+6; int* k = arr+3; do { std::copy(arr, k, std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n"; } while (next_combination(arr, k, end)); }