Kombinatorik: weiße+schwarze Kugeln auf Kisten verteilen



  • (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

Anmelden zum Antworten