Anzahl von Möglichkeiten zur Verteilung von Kugeln in Behälter

[jungh]

Hallo,
ich suche schon seit einigen Stunden ohne mehr oder weniger passende Ergebnisse; ich versuche, die Anzahl von Möglichkeiten zu finden, eine gegebene Anzahl nicht unterscheidbarer Bälle auf unterscheidbare Behälter, die jeweils ein unterschiedliches Fassungsvermögen haben, zu verteilen. Den passenden Ansatz dazu habe ich nach einigen Minuten schon gefunden, jedoch habe ich keine Idee, wie (und ob) man das in Java umsetzen kann: http://narkive.com/9a0CvErb.2 . Bisher habe ich ein nicht ganz komplettes Programm, es kann zwar die Möglichkeiten, die Bälle auf Gefäße aufzuteilen, errechnen, jedoch wird dabei noch kein Limit für die Größe/das Fassungsvermögen der Behälter beachtet.

Beispiel: 4 Bälle, 3 Behälter (Behälter 1 kann max. 2 Bälle beinhalten, B2 und B3 max. 3 Stück)

Die Möglichkeiten wären dann:

2 1 1
1 2 1
1 1 2
1 3 0
1 0 3
0 3 1
0 1 3
0 2 2


Mein bisheriger Code (der jedoch vermutlich komplett auseinandergenommen werden muss):

public static void main(String[] args){
        int kugeln = 4, behaelter = 3;
       
           long start = System.currentTimeMillis();
           BigInteger counter = new BigInteger("0"), bi1, bi2, bi3;
            
           bi1 = fakultaet(kugeln+behaelter-1);
           bi2 = fakultaet(behaelter-1);
           bi3 = fakultaet(kugeln);
           counter = bi1.divide(bi2.multiply(bi3));
           long end = System.currentTimeMillis()-start;
           System.out.printf("Kugeln: %d, Behälter: %d, Permutationen: %d   |   ", kugeln, behaelter, counter);
    }
   
    private static BigInteger fakultaet(int n){
        BigInteger fakultaet = new BigInteger("1");
       
        for(int i = 1; i <= n; i++)
            fakultaet = fakultaet.multiply(new BigInteger(Integer.toString(i)));
       
        return fakultaet;
    }

Vielen Dank für Antworten!

 

[jungh]

Nachtrag: Ein möglicher Lösungsansatz wäre, nicht direkt die Anzahl der Möglichkeiten mit Beachtung des Fassungsvermögens zu berechnen, sondern erst einmal jede Kombination ohne Behältervolumen, da danach ja einfach alle ausgeschlossen werden können, die das Volumen in einem der Behälter überschreiten...; ich habe jedoch keine Idee, wie man an so etwas herangehen sollte, außer mit einer rekursiven Funktion die sich entsprechend der Anzahl von Behältern selbst aufruft

 

[Neumi5694]

(in deiner Liste oben fehlen noch mindestens 2 Kombinationen: 202 und 220)
Das mathematische Problem kenne ich nicht, kann dir deswegen auch nichts über die direkte Lösung sagen
Für eine Simulation hätte ich hingegen eine Lösung.
Erstelle hierzu folgende rekursibe Funktion:

    /**
     * Annahmen ohne Fehlerbehandlung: containers ist nicht null, alle Werte in containers sind >= 0, nBalls >=0
     * @param nBalls Zu verteilende Elemente
     * @param containers Liste der Container-Fassungsvermögen
     * @return Alle möglichen Kombinationen, die Elemente auf die Container aufzuteilen
     */
private static ArrayList<ArrayList<Integer>> splitBallsInto(int nBalls, List<Integer> containers) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//Prüfung 1: nBalls < 1?
//dann ist das einzige Ergebnis eine ArrayList<Intger> der Länge containers.size() mit lauter 0.
//Prüfung 2: nBalls > Summe aller Container ?
//dann gibt es keine Lösung
//Prüfung 3 (Auch Abbruch der Rekursion): Gibt es weniger als 2 Container?
//Dann müssen alle Bälle zwangsläufig im ersten liegen, es gibt also nur eine Lösung
//ansonsten:
//int maxBallsInContainer = Math.min(nBalls, containers.get(0));
        for (int ballsInContainer = 0; ballsInContainer <= maxBallsInContainer ; ballsInContainer++) {
            int restBalls  = nBalls - ballsInContainer;
            for (ArrayList<Integer> oneResult :
    splitBallsInto(restBalls, containers.subList(1, nBalls))) {
        //jedem Ergebnis den Wert ballsInContainer  voranstellen (per add(0, ballsInContainer)) und das Ergebnis danach der Liste result hinzufügen
   }
}
    return result;
}

Ich hatte das fertig ausprogrammiert, nachträglich hab ich ein paar Zeilen rausgelöscht und durch Kommentare ersetzt, damit du auch noch was zu tun hast.

 

[Neumi5694]

Edit: Die Sublist muss natürlich als EndIndex die Länge der ursprünglichen Containerliste verwenden und nicht die Ballanzahl