Kombinatorik Algorithmus - Denkblockade

Samuirai

Hey,

Ich brauche einen Algorithmus der mir alle Kombonationen aus einer bestimmten Zahlenreihe gibt.

Beispiel:
3 aus 5

0 | 1 | 2
0 | 1 | 3
0 | 1 | 4
0 | 2 | 3
0 | 2 | 4
0 | 3 | 4
1 | 2 | 3
1 | 2 | 4
1 | 3 | 4
2 | 3 | 4

Das ist erstmal kein Problem. Mit ein paar verschachtelten For-Schleifen erhalte ich das Ergebnis

for(int i=0; i<5; i++)
	{
		for(int j=i+1; j<5; j++)
		{
			for(int k=j+1; k<5; k++)
			{
				cout << i << " | " << j << " | " << k << endl;
			}
		}
	}

Da ich aber das Ergebnis beliebig brauche, also n aus k, brauch ich einen anderen Algorithmus.
Mir ist klar das er rekursiv sein muss, aber mir fehlt irgendwie das rekursive Denken total.
Seit 4 Tagen grübel ich nun, bin am Bäume und Tabellen aufzeichnen, aber ich bekomms nicht gebacken.
Hab schon verschiedene Ansätze gehabt:
+ Startarray festlegen und hinterste Element immer erhöhen, bis max, dann das Element davor erhöhen und danach wieder das hinterste Element bis zum maximal,...

Dann hatte ich noch diesen Ansatz:

void combi(int start, int max,int anz)
{
	if(anz>0)
	{
		for(int i=start; i<max; i++)
		{
			combi(start+1,max,anz-1);
		}
	}
}

Ich dachte das wär er, aber ich komm jetzt trotzdem nicht weiter.

Hab auch schon gegoogelt, finde aber nur Permutation und weiß auch nicht genau wie der Name meines Problems ist.

Für Python habe ich eine Algorithmus gefunden und wollte diesen in C++ umschreiben, aber ich verstehe die Syntax nicht ganz:

def comblist(n,m,b=1,l=[0]):
    L = len(l)
    if L == m+1:
        return [l[1:]]
    else:
        c = l[-1]
        q,r = c+1,min(c+b+m,n+1)
        cl = []
        for i in range(q,r):
            cl.extend(comblist(n,m,b+1,l+[i]))
        return cl

print comblist(5,3)

Kann mir jemand helfen?
Kennt jemand den Pseudocode dafür?
Ich bin auch schon dankbar für einen kleinen Denkanstoß. Ich hab das Gefühl ich seh vor lauter Bäumen den Wald nicht

Viele Grüße,
Samuirai

Blue-Tiger

Samuirai schrieb:

Hab auch schon gegoogelt, finde aber nur Permutation und weiß auch nicht genau wie der Name meines Problems ist.

Das ist genau was du willst: alle Permuationen einer gewissen Menge

Wenn du das googelst findest genug Beispiele. Das Problem hat man sogar so haeufig, dass es dafuer eine eigene STL-Funktion gibt: http://www.cppreference.com/wiki/stl/algorithm/next_permutation

EDIT: hoppla, ist ja doch nicht was du willst
Was du machen koenntest: erstell alle Permutationen, merk dir aber immer nur die hintersten 3 Zahlen der aktuellen Permutation. (Damit erhaelst du Ergebnisse doppelt, aber die kannst du ja leicht eliminieren, z. B. durch std::unique oder std::set).

volkard

Blue-Tiger schrieb:

Was du machen koenntest: erstell alle Permutationen, merk dir aber immer nur die hintersten 3 Zahlen der aktuellen Permutation. (Damit erhaelst du Ergebnisse doppelt, aber die kannst du ja leicht eliminieren, z. B. durch std::unique oder std::set).

Bei 3 aus 26 (3 Buchstaben) leider nicht doppelt, sondern 155112100433309859840000-fach.
Ich glaube, da reicht mein RAM nicht. Ups, die Festplatte auch nicht, Mist, muß mit noch schnell (bei 26 Byte pro Zwischenergebnis) 10 Billiarden Terabyte-Platten kaufen und ein kleines Kraftwerk. Ich fürchte, Amazon hat beides nicht vorrätig. Was mache ich denn da jetzt?

Samuirai

Hey,
vielen Dank schonmal.
Permutation ist doch einfach nur das vertauschen, aber ich wills ja nicht vertauschen.
[1 | 2 | 3] ist das gleiche wie [3 | 2 | 1]
Es muss doch iwie so gehen, dass man die for-Schleifen in eine Rekursive Funktion packt.
Was ist denn an meinem Ansatz falsch. Müsste es nicht so gehen?
Was mach ich falsch?

VIele Grüße,
Samuirai

Blue-Tiger

volkard schrieb:

Blue-Tiger schrieb:

Was du machen koenntest: erstell alle Permutationen, merk dir aber immer nur die hintersten 3 Zahlen der aktuellen Permutation. (Damit erhaelst du Ergebnisse doppelt, aber die kannst du ja leicht eliminieren, z. B. durch std::unique oder std::set).

Bei 3 aus 26 (3 Buchstaben) leider nicht doppelt, sondern 155112100433309859840000-fach.
Ich glaube, da reicht mein RAM nicht. Ups, die Festplatte auch nicht, Mist, muß mit noch schnell (bei 26 Byte pro Zwischenergebnis) 10 Billiarden Terabyte-Platten kaufen und ein kleines Kraftwerk. Ich fürchte, Amazon hat beides nicht vorrätig. Was mache ich denn da jetzt?

Ergebnis einfach gleich in ein std:set stopfen, und dann halt ganz lang warten bis die ganzen Permutationen durch sind. Aber ich seh schon, du willst drauf hinaus dass es 'ne bessere Loesung gibt, also warum nicht raus damit?

volkard

Blue-Tiger schrieb:

Aber ich seh schon, du willst drauf hinaus dass es 'ne bessere Loesung gibt,

Nö, eigentlich wollte ich darauf hinaus, daß man sich nicht immer an die Standardbibliothek hängen muß.

Blue-Tiger schrieb:

also warum nicht raus damit?

Weil ich sofort sah, daß next_permutation nicht paßt. Und ich hatte selber keine Lösung, das Problem löst nämlich tatsächlich Denkblockaden aus.

#include <iostream>
using namespace std;

void print(int feld[],int anzahl){
	for(int i=0;i<anzahl;++i)
		cout<<feld[i]<<' ';
	cout<<'\n';
}

void test(int feld[],int n,int k,int pos,int val){
	if(pos==k)
		return print(feld,k);
	for(int i=val;i<n;++i){
		feld[pos]=i;
		test(feld,n,k,pos+1,i+1);
	}
}

int main(){
	int feld[3];
	test(feld,5,3,0,0);
	return 0;
}

Samuirai

Super
Vielen Dank, dass funktioniert perfekt.
Jetzt den Code mal genau anschaun und verstehen, wo meine Denkfehler waren.
Vielen Dank,

Samu

knivil

Muss es denn in C oder C++ sein? Mir fallen da zwei Zeilen Haskellcode ein, kann sie aber grad nicht testen.

Samuirai

Es sollte schon sehr schnell laufen. Soweit ich weiß hat Python 3.1 das auch direkt implementiert.
Ich schreibe am liebsten in C++, da das natürlich nur ein Teil des gesamten Algorithmus ist, und ich nicht einfach so ausweichen kann.
Vielen Dank an alle

Viele Grüße,
Samu

HumeSikkins

volkard schrieb:

Weil ich sofort sah, daß next_permutation nicht paßt. Und ich hatte selber keine Lösung, das Problem löst nämlich tatsächlich Denkblockaden aus.

@Volkard
Hab vor Jahren hier mal ne next_permutation-ähnliche Variante von next_combination
geschrieben:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-193087 (letzter Beitrag)

Achtung: Ist aber etwas buggy, d.h. funktioniert so nicht, falls die Eingabesequenz Elemente doppelt enthält. Ich hatte den Code irgendwann auch
mal gefixed, finde es aber nicht mehr.

volkard

HumeSikkins schrieb:

Hab vor Jahren

In der Tat!

HumeSikkins schrieb:

next_permutation-ähnliche Variante von next_combination

Ja, die hatte ich auch im Auge. Aber ich dillematisierte furchtbar zwischen "n Elemente nehmen, wo nur k gebraucht werden" und "nur rekursiv gehen und die Nutzanwendung per Dingens bis runter reinschubsen"; ich habe mich für "bald gibt es ja alles, und reinschubsen tut nicht mehr so weh (vielleicht)" entschieden.

knivil

Hier der versprochene Zweizeiler in Haskell:

outOf 0 _ = [[]]
outOf n xs = [ (a:as) | a <- xs, as <- outOf (n-1) $ tail $ dropWhile (/=a) xs ]

*Main> 3 `outOf` [0..4]
[[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

Diese Loesung funktioniert nur mit echten Mengen. Diese muessen aber nicht sortiert sein. Bei doppelten Eintraegen (Multiset) bildet man die Elemente auf ihre Indizes ab und wendet `outOf` auf die Indexmenge an. Da es in Haskell auch arrays gibt, laesst sich diese Abbildung effizient implementieren.

Aus dem obigen Code kann man auch eine Implementation fuer C++ (oder aehnliche ableiten). Dabei gewinnt man mittels a <- xs einen Iterator, den man direkt in `outOf` weiterverwenden kann. tail $ dropWhile (/=a) ... dient nur dafuer, den entsprechenden "Iterator" auf das Element hinter dem gerade ausgewaehlten zu setzen. Dadurch waere eine entsprechende Implementation mit Iteratoren effizienter.

Vielleicht werde ich es mal in C++ umsetzen.

knivil schrieb:

Hier der versprochene Zweizeiler in Haskell
[...]

Gibt's in Haskell kein amb ?

knivil

Meinst du McCarthy's Ambiguous Operator? Und was sollte er besser machen? Der vorgestellte Zweizeiler benutzt kein backtracking.

knivil schrieb:

Meinst du McCarthy's Ambiguous Operator?

Ja.

knivil schrieb:

Und was sollte er besser machen? Der vorgestellte Zweizeiler benutzt kein backtracking.

Schon klar, aber ich versuch immer gern mal einen Ansatz, für den ich nicht nachdenken muss. Besser machen geht bekanntlich später immer noch.

knivil

Und wie wuerdest du es mittels amb formulieren, wenn dieser Operator zu Verfuegung steht?

Besser machen geht bekanntlich später immer noch.

Nur macht es kaum einer.