Programm, um alle Kombinationen von Ball-Box-Anwendung zu bekommen

Question

Ich bin neu in Kombination und Permutation bezogene Algorithmen. Hat jemand irgendwelche Gedanken darüber, wie man dieses klassische Problem lösen kann? Es gibt 3 Boxen (A, B, C) und 10 Bälle (1,2,3, ..., 10), wir wollen alle Bälle in die Boxen legen. Das Ergebnis sollte {Box A: Ball 1; Kasten B: Ball 2,3,4; Feld C: Ball 5 6 7 8 9 10}, {Feld A: Ball 1 2; Kasten B: Ball 3 4 5; Kasten C: 7 8 9 10}, .... Ich möchte alle Kombinationen erhalten (nicht die Anzahl der verschiedenen Kombinationen).
Außerdem, wenn es eine Einschränkung gibt, dass jede Box höchstens 4 Bälle enthält?

Vielen Dank.

Answer 1

Sie können den ersten Ball in einer von drei Boxen, so dass Sie drei Varianten haben.
Es gibt drei Varianten für den zweiten Ball, drei für den dritten und so weiter.

Sie sind unabhängig, Sie haben also 3^10 Varianten und jede Variante hat 1: 1-Mapping mit einer Nummer im Bereich 0..3^10-1.

Betrachte Nummer im ternären Zahlensystem, also k-te ternäre Ziffer der Zahl sagt uns, welche Box (a = 0, b = 1, c = 2) k-ten Ball gehört.

Beispiel 3 Kugeln:
Number 14 = 112 ternäre, so erste Kugel in C, zweite und dritten in B

Für Fall begrenzten Kastengröße einfachen Ansatzes ist rekursive Erzeugung - Argumente der Rekursion sind Liste der verfügbare Bälle und aktuelle Kombination (Liste der Boxen mit Bällen und freien Plätzen).