Перестановка элементов N в ячейках?

Question

Я пытаюсь найти все возможные способы расположения N элементов в блоках A, где не имеет значения порядок ящиков и порядок элементов, но имеет значение, какие элементы находятся вместе в одном поле. Например, ожидаемый результат на 3 ящика и 3 элементов ниже:

  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] 

Это аналогичные, но более и более общая задача, чем тот просил здесь: Enumeration of combinations of N balls in A boxes?

Я бы очень признателен за любой вклад на этот вопрос, предпочтительно используя язык python.

Answer 1

Они называются set partitions. Рекурсивную функцию можно найти здесь: Set partitions in Python. Несколько более эффективным «снизу вверх» рекурсивная версия такова:

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) 

Выход:

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

Это не дает пустые коробки, как в вашем примере, но это тривиально, чтобы увеличить генератор к Сделай так.

Для итерационного алгоритма см. «Эффективное генерирование заданных разделов» Майкла Орлова (2002). Обратите внимание, что количество установленных разделов быстро растет , поэтому даже итеративный алгоритм займет некоторое время, чтобы перечислить все разделы даже небольшого размера.

Для количества число разбиений множества, не создавая их, увидеть Bell Numbers (OEIS A000110). Ниже приведена одна возможная (не очень эффективная) процедура вычисления чисел Белла в Python:

def bell(n): 
    "-> the n'th Bell number." 
    assert n >= 0, n 

    # loop will execute at least once 
    for b in bell_sequence(n): 
     pass 

    return b 

def bell_sequence(n): 
    """Yields the Bell numbers b(0),b(1)...b(n). 

    This function requires O(n) auxiliary storage. 
    """ 
    assert n >= 0, n 
    # compute Bell numbers using the triangle scheme 
    yield 1 # b(0) 

    row = [1] + (n-1)*[0] 

    for i in range(0, n): 
     row[i] = row[0] 

     for k in reversed(range(i)): 
      row[k] += row[k + 1] 

     yield row[0] # b(i + 1)