Kombinatorik: weiße+schwarze Kugeln auf Kisten verteilen



  • Hallo zusammen,

    ich habe hier ein Problem, dass ich auf eine Kombinatorikproblem reduziert habe, komme aber nicht weiter.
    Ich habe n (ununterscheidbare) weiße Kugeln, m (ununterscheidbare) schwarze Kugeln und k (unterscheidbare) Kisten.
    Ich suche alle (unterscheidbaren) Kombinationsmöglichkeiten die Kugeln auf die Kisten zu verteilen.
    Es müssen immer alle Kugeln auf die Kisten verteilt sein.
    Eine Kiste kann 0 bis n+m Kugeln enthalten.

    Vielen Dank!

    Meine Überlegung dazu:

    1. Fange mit Kiste l=0 an und Fülle diese mit allen Kugeln.
    2. Wähle eine weiße Kugel(schwarz, falls weiß nicht vorhanden) und schiebe diese nach und nach durch alle Kisten.
    3. Wenn wir bei der letzten Kiste sind, schiebe die gewählte Kugel wieder an den Anfang (hier habe ich glaube ich ein Problem im Algorithmus)
    4. Wenn die Kiste l leer ist, wiederhole bei 1. (aber mit Kiste l+1)
      ...
    int n = 1;
    int m = 1;
    const int k_max = 3;
    int kombinationNr = 0;
    pair<int, int> Kisten[k_max]; //Anzahl weißer Kugeln, Anzahl schwarzer Kugeln
    
    void printKisten() {
    	cout << "KombinationNr = " << kombinationNr++ << endl;
    	for (int i = 0; i < k_max; i++) {
    		cout << "Kiste #" << setw(2) << i << ": " << Kisten[i].first << " / " << Kisten[i].second << endl;
    	}
    }
    
    void test() {
    	//Starte lauf mit erster Kiste = voll
    	Kisten[0].first = n;
    	Kisten[0].second = m;
    
    	int k = 0; //aktuell betrachtet Kiste
    	int l = 0; //rücksprung merken
    
    	printKisten();
    	//Solange letzte Kiste nicht voll ist
    	while (Kisten[k_max - 1].first + Kisten[k_max - 1].second != n + m) {
    		//Wenn nicht letzte Kiste
    		if (k < k_max - 1) {
    			//In die nächste Kiste Schieben, erst weiß
    			if (Kisten[k].first > 0) {
    				Kisten[k].first--;
    				Kisten[k + 1].first++;
    			}
    			//dann schwarz
    			else if (Kisten[k].second > 0) {
    				Kisten[k].second--;
    				Kisten[k + 1].second++;
    			}
    			printKisten();
    			k++;
    		}
    		//letzte Kiste
    		else {
    			//Wenn noch weiße vorhanden, dann die weiße eins weiter starten
    			if (Kisten[l].first > 0) {
    				Kisten[k].first--;
    				Kisten[l + 1].first++;
    			}
    			//Keine weiße, aber noch schwarze, dann einen "Übertrag" machen
    			else if (Kisten[l].second > 0) {
    				Kisten[k].first=0;
    				Kisten[l].first=n;
    				Kisten[l].second--;
    				Kisten[l + 1].second++;
    				printKisten();
    			}
    			//Gar keine Kugeln mehr, dann von vorne mit einer Kiste weniger
    			else {
    				l++;
    				Kisten[k].first = 0;
    				Kisten[k].second = 0;
    				Kisten[l].first = n;
    				Kisten[l].second = m;
    				//Wenn noch weiße vorhanden, dann die weiße eins weiter starten
    				if (Kisten[l].first > 0) {
    					Kisten[k].first--;
    					Kisten[l + 1].first++;
    				}
    			}
    			k = l;
    		}
    	}
    }
    


  • Kann sein, dass ich Fälle übersehen habe. Also bitte nochmal nachdenken

    Kiste = {AnzahlWeißeKugeln, AnzahlSchwarzeKugeln}
    Zustand = {Alle Kisten mit ihren Kugeln}
    Zustandsliste = Liste an bereits besuchten Möglichkeiten:

    Mein Gedanke wär:

    1. Alle Kugeln in eine Kiste tun. Das ist der Startzustand. Diesen in Zustandsliste tun.
    2. Bei Zustandsliste bei Index 0 beginnen
    3. Mit jedem Zustand in der Liste: Neue Zustände generieren:
    • Eine weiße Kugel von Kiste 0 in jeweils einmal in jede andere Kiste tun. -> neue Zustände
    • Eine schwarze Kugel von Kiste 0 in jeweils einmal jede andere Kiste tun -> neue Zustände
    1. Neue Zustäde zur Zustandsliste hinzufügen.
    2. Weiter bei 3, weil die Liste gewachsen ist.

    Terminiert wenn Anfangskiste leer ist.

    Der Algo verbraucht viel Speicher, aber die einzige Alternative die mir gerade eingefallen ist, ist rekursiv. Da würde jeder Zustand wieder zurückgefuttert in die Funktion die Zustände produziert bis Kiste 0 leer ist.
    EDIT: wenn man die Liste von vorne löscht, wenn man sie abarbeitet geht der Speicherverbrauch sogar ist der Verbrauch geringfügig kleiner, und die Ergebnisse gleich ausgbit.



  • Hallo, danke erstmal für die Antwort. Habe versucht das mal umzusetzen, bekomme aber nicht das richtig Ergebnis. Vermutlich habe ich den Algo nicht wie von dir gedacht umgsetzt?

    void ZustandsListe() {
    	const int n = 1;//Anz weiße Kugeln
    	const int m = 1;//Anz schwarze Kugeln
    	const int k_max = 2; //Anz Kisten
    
    	//Zustandsliste
    	deque<map<int, pair<int, int>>> states; //map<KistenNr, pair<AnzWeißeKugeln, AnzSchwarzeKugeln>>
    
    	//Startzustand
    	map<int, pair<int, int>> startState;
    	startState[0].first = n;
    	startState[0].second = m;
    
    	//Mit Startzustatnd Anfangen
    	states.push_back(startState);
    	
    	//Terminiert wenn Anfangskiste leer
    	while (startState[0].first + startState[0].second > 0) {
    		//Anzahl Zustände für diese Iteration merken
    		size_t prevSize = states.size();
    		for (int s = 0; s < prevSize; s++) {
    			//Falls weiße kugeln vorhanden
    			if (startState[0].first > 0) {
    				//Für alle anderen Kisten einenen neuen Zustand erstellen
    				for (int i = 1; i < k_max; i++) {
    					map<int, pair<int, int>> newState;
    					newState[0].first = startState[0].first - 1;					
    					newState[0].second = startState[0].second;
    					newState[i].first++;
    					states.push_back(newState);
    				}
    			}
    			//Falls schwarze kugeln vorhanden
    			if (startState[0].second > 0) {
    				//Für alle anderen Kisten einenen neuen Zustand erstellen
    				for (int i = 1; i < k_max; i++) {
    					map<int, pair<int, int>> newState;
    					newState[0].first = startState[0].first;
    					newState[0].second = startState[0].second - 1;
    					newState[i].second++;
    					states.push_back(newState);
    				}
    			}
    		}
    		//Kugeln in erster Kiste reduzieren
    		if (startState[0].first > 0)
    			startState[0].first--;
    		if (startState[0].second > 0)
    			startState[0].second--;
    	}
    }
    


  • Kannst du nicht einfach

    (n+k1n)×(m+k1m){n + k -1 \choose n} \times {m + k - 1 \choose m}

    rechnen?

    Oder irre ich da gerade?



  • Ich dachte er will alle Kombination ausgeben, nicht die Anzhal der möglichen Kombis.

    Ich schau mir den code mal an



  • Ja, wollte alle kombos durchiterieren. Wenn wir die Anzahl haben, dann hilft das aber zum verifizieren des algos



  • @JaykopX sagte in Kombinatorik: weiße+schwarze Kugeln auf Kisten verteilen:

    Wenn wir bei der letzten Kiste sind, schiebe die gewählte Kugel wieder an den Anfang (hier habe ich glaube ich ein Problem im Algorithmus)

    Ja, Du hast ein Problem. Da ist keine Abbruchbedingung.



  • (Erste Antwort)

    @JaykopX sagte in Kombinatorik: weiße+schwarze Kugeln auf Kisten verteilen:
    Finde es unglücklich dass du eine map verwendest für die kisten.
    würde lieber einen fixen array oder vector nehmen und den bei erstellung die größe geben. Kein Beinbruch, aber schwieriger nachzuvolliehen.

    mit while (startState[0].first + startState[0].second > 0) könnte es vielleicht sein dass du den letzten satz an kombination verpasst, wo kiste 0 leer ist.



  • Ich hab grad testhalber mein algo implementiert.
    Der produziert leider duplikate.

    Er findet alle Optionen, aber mehrfach -.-.
    Man könnte natürlich prüfen ob die schon existieren, aber das wäre nicht meine erste Wahl.
    Ich muss jetzt aber erstmal was anderes machen.

    hmmm.



  • Leider ist das sehr ineffizient für wirklich große Zahlen, weil ich immer raussuche ob es duplikate Resultate sind. (1 sekunde für 15876 ergebnisse auf meiner CPU im Release Build, 7 Sekunden für 44100. IMHO grausig)
    Wollte aber bevor ich mich aus dem Thread zurückzieh trotzdem mein Ansatz testen und die Implementierung hier lassen, auch wenn ich nicht zufrieden bin.

    Vielleicht hat ja jemand noch nen cleverern Vorschlag.

    #include <boost/math/special_functions/binomial.hpp>
    
    #include <deque>
    #include <map>
    #include <vector>
    #include <utility>
    #include <iostream>
    
    struct Container
    {
        int white = 0;
        int black = 0;
    
        void print() const
        {
            std::cout << "(" << black << ", " << white << ")";
        }
    
        bool operator==(Container const& other) const
        {
            return other.white == white && other.black == black;
        }
    };
    
    std::vector <Container> createContainers(std::size_t const anzahl)
    {
        return std::vector <Container>(anzahl);
    }
    
    std::vector <std::vector <Container>> makeCombinations(std::vector <Container> const& containers)
    {
        std::vector <std::vector <Container>> result;
    
        // redistribute a white
        for (std::size_t i = 1; containers[0].white != 0 && i != containers.size(); ++i)
        {
            auto cpy = containers;
            cpy[0].white--;
            cpy[i].white++;
            result.push_back(std::move(cpy));
        }
    
        // redistribute a black
        for (std::size_t i = 1; containers[0].black != 0 && i != containers.size(); ++i)
        {
            auto cpy = containers;
            cpy[0].black--;
            cpy[i].black++;
            result.push_back(std::move(cpy));
        }
    
        return result;
    }
    
    bool statesAreSame(std::vector <Container> const& lhs, std::vector <Container> const& rhs)
    {
        // can technically be omited
        if (lhs.size() != rhs.size())
            return false;
    
        for (std::size_t i = 0; i != lhs.size(); ++i)
            if (lhs[i] != rhs[i]) return false;
        return true;
    }
    
    int main()
    {
        const int n = 4;//Anz weiße Kugeln
        const int m = 4;//Anz schwarze Kugeln
        const int k_max = 6; //Anz Kisten
    
    	auto expected = boost::math::binomial_coefficient<double>(n+k_max-1, n) * boost::math::binomial_coefficient<double>(m+k_max-1, m);
    
        std::cout << "expected: " << expected << "\n";
    
    	// Kisten erstellen
        using StateType = std::vector <Container>;
        std::vector <StateType> states;
    
        states.reserve(expected);
        states.push_back(createContainers(k_max));
    
        // im Startzustand die ersten Container mit allen Bällen füllen:
        states[0][0] = {n, m};
    
        for (std::size_t iter = 0; iter != states.size(); ++iter)
        {
            auto fresh = makeCombinations(states[iter]);
    
            // Only inserts non-duplicates
            for (std::size_t i = 0; i != fresh.size(); ++i)
            {
                bool found = false;
                for (std::size_t j = 0; j != states.size(); ++j)
                {
                    if (statesAreSame(fresh[i], states[j]))
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                    states.push_back(fresh[i]);
            }
        }
        std::cout << "got: " << states.size() << "\n";
    
        /*
        for (auto const& i : states)
        {
            for (auto const& k : i)
                k.print();
            std::cout << "\n";
        }
        */
    }
    


  • Ist die Aufgabe nicht mehr oder weniger trivial? Also vielleicht hab ich da jetzt nen Denkfehler, aber...
    Man fängt mit der ersten Kiste an. Hier gibt es (N + 1) * (M + 1) Kombinationen: 0...N weisse Kugeln kombiniert mit 0...M schwarze Kugeln in die erste Kiste. Und ab da ist das ne ganze einfache Rekursion: also in der zweiten Kiste landen jetzt 0...verbliebene_N weisse und 0...verbliebene_M schwarze Kugeln. Ebenso für die dritte Kiste, vierte Kiste etc.

    #include <vector>
    #include <stdio.h>
    
    bool do_print_contents = true;
    
    struct box {
    	unsigned white;
    	unsigned black;
    };
    
    void print_contents(unsigned box_count, box const* boxes) {
    	char const* delim = "";
    	for (unsigned i = 0; i < box_count; i++) {
    		auto const b = boxes[i];
    		printf("%s(%u,%u)", delim, b.white, b.black);
    		delim = ", ";
    	}
    	printf("\n");
    }
    
    unsigned long long iterate_combinations(unsigned n, unsigned m, unsigned box_count, box* boxes, unsigned pre_filled_count) {
    	if (pre_filled_count < box_count) {
    		box& my_box = boxes[pre_filled_count];
    
    		unsigned long long combinations = 0;
    		for (unsigned my_n = 0; my_n <= n; my_n++) {
    			for (unsigned my_m = 0; my_m <= m; my_m++) {
    				my_box.white = my_n;
    				my_box.black = my_m;
    				combinations += iterate_combinations(n - my_n, m - my_m, box_count, boxes, pre_filled_count + 1);
    			}
    		}
    		return combinations;
    	} else {
    		if (do_print_contents)
    			print_contents(box_count, boxes);
    		return 1;
    	}
    }
    
    unsigned long long iterate_combinations(unsigned n, unsigned m, unsigned box_count) {
    	std::vector<box> boxes;
    	boxes.resize(box_count);
    	return iterate_combinations(n, m, box_count, &boxes[0], 0);
    }
    
    int main() {
    	auto const total = iterate_combinations(5, 6, 7);
    	printf("total combinations: %llu\n", total);
    }
    

    Wenn man sich das Ergebnis auf Windows auf der Konsole ausgeben lässt ist es auch reichlich langsam. Das liegt aber an der Ausgabe. Und selbst wenn man es in ein File schreibt geht noch die meiste Zeit beim Schreiben/Formatieren drauf.
    Debug Build:

    • 1,369 Mio Kombinationen ohne Schreiben = 0,07 Sekunden
    • 1,369 Mio Kombinationen mit Schreiben in File = 12 Sekunden

    Release Build:

    • 1,369 Mio Kombinationen mit Schreiben in File = 4 Sekunden

    ps: printf, weil mit std::cout 2~3 mal langsamer. libfmt hab ich nicht ausprobiert, wäre aber interessant.

    EDIT: Ja, der Code hat einen Fehler, ist mir auch gerade aufgefallen. Weil ich Kugeln übrig lasse. Ist aber leicht zu beheben, man muss einfach nur wenn nur mehr eine Kiste übrig ist alle verbleibenden Kugeln da reinpacken. Korrektur kommt gleich (neuer Beitrag).



  • Nachdem libfmt ans nuget Package verfügbar ist, hab ich es auch noch schnell ausprobiert...

    Release Build mit libfmt Ausgabe:

    • 1,369 Mio Kombinationen mit Schreiben in File = 2,06 Sekunden


  • Korrektur:

    unsigned long long iterate_combinations(unsigned n, unsigned m, unsigned box_count, box* boxes, unsigned pre_filled_count) {
    	box& my_box = boxes[pre_filled_count];
    
    	if ((pre_filled_count + 1) < box_count) {
    		unsigned long long combinations = 0;
    		for (unsigned my_n = 0; my_n <= n; my_n++) {
    			for (unsigned my_m = 0; my_m <= m; my_m++) {
    				my_box.white = my_n;
    				my_box.black = my_m;
    				combinations += iterate_combinations(n - my_n, m - my_m, box_count, boxes, pre_filled_count + 1);
    			}
    		}
    		return combinations;
    	} else {
    		my_box.white = n;
    		my_box.black = m;
    		if (do_print_contents)
    			print_contents(box_count, boxes);
    		return 1;
    	}
    }
    

    Rest unverändert.



  • Super, danke hustbaer! Bisher läuft es wie ich es wollte.


  • Mod

    @hustbaer Dein Code löst nicht die im OP beschriebene Aufgabe. Es gibt keine Million Kombinationen. Kombinatorisch sieht der Beweis so aus, dass man die schwache k-Komposition von n und m berechnet und multipliziert (da ausgehend von der Fragestellung die Verteilungen unabhaenging sind). Das Ergebnis ist

    (n+k1n)×(m+k1m)=(5+715)×(6+716)=462×924=426888\binom{n + k - 1}{n} \times \binom{m + k - 1}{m} = \binom{5 + 7 - 1}{5} \times \binom{6 + 7 - 1}{6} = 462 \times 924 = 426888

    Was Dein Code berechnet ist die Anzahl der möglichen unvollständigen Verteilungen, und er ergibt den richtigen Wert mit der entsprechenden Korrektur:

            ....
    	} else {
    +                boxes[box_count-1].white += n;
    +                boxes[box_count-1].black += m;
    		if (do_print_contents)
    			print_contents(box_count, boxes);
    

    Die unvollständigen Verteilungen ergeben sich indem wir eine 'extra box' einfügen, die in jedem Durchlauf exakt die überschüssigen Kugeln aufnimmt:

    (n+kn)×(m+km)=(5+75)×(6+76)=462×924=1359072\binom{n + k}{n} \times \binom{m + k}{m} = \binom{5 + 7}{5} \times \binom{6 + 7}{6} = 462 \times 924 = 1359072

    Edit: @wob ich war ganz anscheinend nicht der erste, der die compositions Wikipedia Seite studiert hat... 😝

    Edit^2: Verdammt, ich war ja total uebereifrig und sehe nicht, dass er sich schon laengst korrigiert hat...



  • Ich habe mich gefragt ob ich eine effiziente nicht rekursive Lösung finden kann. (Weil ich dummerweise rekursion komplett ausgeschlossen hab am Anfang)
    Es hat mich einfach nicht aufgehört zu wurmen.

    Mittlerweile hab ich eine für k=2, aber darüber (k>2) muss ich nochmal nachdenken.



  • @5cript
    Man kann den rekursiven Algorithmus ja in eine nicht-rekursive Form bringen. Er wird dadurch bloss komplizierter zu formulieren und zu lesen. Speziell wenn man nicht unnötig viel Speicher verbrauchen will. Ich sehe auch keinen Vorteil darin.



  • @hustbaer
    gibt keinen, aber es war eine Herausforderung.
    Außerdem wollte ich die Tragödie von Laufzeitkomplexität da oben nicht stehen lassen und anpassen, dass (wenn auch nicht so effizient wie die Lösung von dir) sie bessere Performance erreicht.

    Aber für k>2 brauchts mehr hirnschmalz und ich habe eine Ahnung wie ich es machen könnte, aber jetzt wo die Woche wieder anfängt weiß ich nicht ob ich lust hab mein Ansatz weiter zu verfolgen.

    Immerhin hab ich mittlerweile rausgefunden, dass in dem Baum den ich aufbau (im Geiste, nicht wortwörtlich, aber das ist im Prinzip was der Algo macht, er baut ein Baum vom Ausgangszustand auf) alle Knoten rausnehmen muss bei dem die Pfadfolge (weiß umverteilt = links im baum = 1, schwarz umverteilt = rechts im baum = 0) nicht geeordnet ist (Kann nicht links von einem knoten weitergehen, wenn ich vorher rechts runter bin), um die Dupikate für k=2 zu "entnehmen". Overhead = ein geführter boolean (oder int) pro Knoten, sowie ein operator>() oder 1 operator==().

    Ich glaube für k>2 ist es ein ähnliches Prinzip.

    Dass Rekursion nicht in Frage kam war ein Denkfehler von mir. Hatte mir wegen Stackoverflows sorgen gemacht, aber als ich mir deine Lösung angesehen habe ist mir aufgefallen dass das absolut unberechtigt war (weil die kombinationsmöglichkeiten explodieren bevor die rekursionstiefe problematisch wird)



  • Für eine effiziente Lösung, müsste man das wohl in drei Schritten machen.

    1. Alle Kombinationen von maximal k Summanden finden, die als Summe n bzw. m ergeben (mit allen Summanden Ganzahl 1 <= s <= n)
    2. Alle Verteilungen dieser zwei Summandenlisten auf die k Kisten erstellen
    3. Das "Kreuzprodukt" aus allen Permutationen ausgeben

Log in to reply