Permutation von Elementen in A-Boxen?

Question

Ich versuche, alle möglichen Wege zu finden, um N Elemente in A-Boxen anzuordnen, wo die Reihenfolge der Boxen und die Reihenfolge der Elemente egal ist, aber es spielt keine Rolle, welche Elemente zusammen in der gleichen Box sind. Zum Beispiel ist das erwartete Ergebnis für 3-Box und 3 Elemente unten:

  box_1  box_2  box_3 
case-1  [1,2,3] []   [] 
case-2  [1,2]  [3]   [] 
case-3  [1,3]  [2]   [] 
case-4  [2,3]  [1]   [] 
case-5  [1]  [2]   [3] 

Dies ist ein ähnliches, aber allgemeineres Problem als die hier gestellt: Enumeration of combinations of N balls in A boxes?

ich für jeden Beitrag sehr dankbar wäre, auf diese Frage vorzugsweise mit Python-Sprache.

Answer 1

Diese heißen set partitions. Eine rekursive Funktion finden Sie hier: Set partitions in Python. dies ein etwas effiziente „bottom-up“ rekursive Version ist:

def generate_partitions(a): 
    a = list(a) 
    n = len(a) 
    partition = [] # a list of lists, currently empty 

    def assign(i): 
     if i >= n: 
      yield [list(part) for part in partition] 
     else: 
      # assign a[i] to an existing part 
      for part in partition: 
       part.append(a[i]) 
       yield from assign(i + 1) 
       part.pop() 

      # assign a[i] to a completely new part 
      partition.append([a[i]]) 
      yield from assign(i + 1) 
      partition.pop() 

    if n: 
     yield from assign(0) 
    else: 
     yield [[]] 


for partition in generate_partitions([1,2,3]): 
    print(*partition) 

Ausgang:

[1, 2, 3] 
[1, 2] [3] 
[1, 3] [2] 
[1] [2, 3] 
[1] [2] [3] 

Dies erzeugt nicht die leeren Kisten wie in Ihrem Beispiel, aber es trivial den Generator zu erweitern tun Sie dies.

Für einen iterativen Algorithmus siehe "Effiziente Generierung von Satzpartitionen" von Michael Orlov (2002). Beachten Sie, dass die Anzahl der festgelegten Partitionen sehr schnell anwächst, sodass selbst ein iterativer Algorithmus einige Zeit benötigt, um alle Partitionen selbst eines Satzes bescheidener Größe aufzulisten.

Um Zählung die Anzahl der eingestellten Partitionen, ohne sie zu erzeugen, finden Sie in der Bell Numbers (OEIS A000110). Hier ist eine mögliche (nicht sehr effiziente) Prozedur zur Berechnung von Bell-Zahlen in Python: