Нет способы размещения K различимых элементов в п различимого коробок

Question

Distinguishable objects into distinguishable boxes

Это очень похоже на этот вопрос, публикуемый. Я пытаюсь получить код python для этого вопроса. Обратите внимание, что это похоже на ключевое различие. то есть Ковш может быть пустым, в то время как другие ведра содержат все элементы. Даже этот случай будет рассматриваться как отдельный случай.

, например:

Рассмотрим у меня есть 3 пунктов А, В, С и 3 ведра В1, В2, В3

В таблице ниже будет показывать ожидаемый результат:

 
B1   B2  B3 
(A,B,C) ()  () 
()  (A,B,C) () 
()   ()  (A,B,C) 
(A)   (B)  (C) 
(A)   (C)  (B) 
(B)   (A)  (C) 
(B)   (C)  (A) 
(C)   (B)  (A) 
(C)   (A)  (B) 
(A,B)  (C)  () 
(A,B)  ()  (C) 
(B,C)  (A)  () 
(B,C)  ()  (A) 
(A,C)  (B)  () 
(A,C)  ()  (B) 
()   (A,B) (C) 
(C)   (A,B) () 
()   (B,C) (A) 
(A)   (B,C) () 
()   (A,C) (B) 
(B)   (A,C) () 
()   (C)  (A,B) 
(C)   ()  (A,B) 
()   (A)  (B,C) 
(A)   ()  (B,C) 
()   (B)  (A,C) 
(B)   ()  (A,C) 

Length is 27. 

>>def make_sets(items, num_of_baskets=3): 
     pass 
>>make_sets(('A', 'B', 'C', 'D', 'E'), 3) 

Я ожидаю, что выход функции даст мне эти комбинации в виде списка списков кортежей. Я говорю это снова, число элементов является переменным, и количество ведер также является переменной.

** Пожалуйста, предоставьте код python для функции make_sets.

Если кто-то может объяснить математическую комбинаторика. Я бы тоже очень признателен. Я потратил более 2 дней на эту проблему, не достигнув определенного решения.

Answer 1

Подумайте о том, чтобы принести предметы по одному, и каждый из них должен выбрать коробку для приземления.

Начните с первого предмета, он имеет n возможных вариантов. Теперь второй предмет входит, у него также есть n возможные варианты выбора. Поскольку элементы и ящики все различимы, нам не нужно беспокоиться о дисконтировании перестановок (как обычно нужно делать для неразличимых элементов). Общее количество различных возможностей до этого момента - n x n.

Принесите третий элемент, он также имеет n вариантов, и поэтому общее количество возможностей теперь n x n x n.

Возможно, вы уже заметили, что ответ n^k, когда у вас есть k.

В приведенном примере n=3 и k=3, поэтому у нас есть 3^3 = 27 возможные способы размещения предметов.

код, чтобы получить список всех действительных комбинаций показано ниже:

import itertools 

def make_sets(items, num_of_boxes=3): 
    allpossible = [] 

    for tup in itertools.product(range(num_of_boxes), repeat=len(items)): 
     boxes = [list() for _ in range(num_of_boxes)] 
     for item, box in zip(items, tup): 
      boxes[box].append(item) 

     allpossible.append(boxes) 

    return allpossible 

for p in make_sets(('A', 'B', 'C')): 
    for box in p: 
     print str(box).ljust(20), 
    print 

Запуск выше распечатывает:

['A', 'B', 'C']  []     []     
['A', 'B']   ['C']    []     
['A', 'B']   []     ['C']    
['A', 'C']   ['B']    []     
['A']    ['B', 'C']   []     
['A']    ['B']    ['C']    
['A', 'C']   []     ['B']    
['A']    ['C']    ['B']    
['A']    []     ['B', 'C']   
['B', 'C']   ['A']    []     
['B']    ['A', 'C']   []     
['B']    ['A']    ['C']    
['C']    ['A', 'B']   []     
[]     ['A', 'B', 'C']  []     
[]     ['A', 'B']   ['C']    
['C']    ['A']    ['B']    
[]     ['A', 'C']   ['B']    
[]     ['A']    ['B', 'C']   
['B', 'C']   []     ['A']    
['B']    ['C']    ['A']    
['B']    []     ['A', 'C']   
['C']    ['B']    ['A']    
[]     ['B', 'C']   ['A']    
[]     ['B']    ['A', 'C']   
['C']    []     ['A', 'B']   
[]     ['C']    ['A', 'B']   
[]     []     ['A', 'B', 'C']  

Answer 2

Обратите внимание, что это соответствует основывают-п чисел (Надеюсь, вы сможете украсить результат). Это решение не зависит от n и k:

n = 5 
k = 7 
a = [0] * k 
def to_base_n(x): 
    num = 0 
    while x is not 0: 
     num *= 10 
     num += x % n 
     x //= n 
    return num 
for i in range(0, n ** k): 
    s = ('%0' + str(k) + 'd') % (to_base_n(i)) 
    x = [list() for _ in range(n)] 
    for i in range(k): 
     x[int(s[i])].append(str(i)) 
    print(x)