k 개의 식별 가능한 항목을 n 개의 식별 가능한 상자에 넣을 수있는 방법이 없음

Question

Distinguishable objects into distinguishable boxes

게시 된이 질문과 매우 비슷합니다. 이 질문에 대한 파이썬 코드를 가져 오려고합니다. 비슷하지만 주요 차이점이 있습니다. 즉 버킷은 비어있을 수 있지만 다른 버킷에는 모든 항목이 포함될 수 있습니다. 이 경우에도 별도의 경우로 간주됩니다. 예

:

이 고려

는 I 3 개 항목 A, B, C 3 버킷을 B1, B2, B3

예상 결과 표시 아래의 표 :

 
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) 

을

튜플 목록 목록 형태로 이러한 조합을 제공하는 함수의 출력을 기대합니다. 다시 말하지만 항목의 수는 가변적이며 버킷 수는 가변적입니다.

** make_sets 함수에 파이썬 코드를 제공하십시오.

누군가가 수학 조합론을 설명 할 수 있다면. 나는 그것을 또한 크게 감사 할 것이다. 나는 명확한 해결책에 도달하지 않고이 문제에 2 일 이상을 보냈다.

Answer 1

항목을 하나씩 가져 오는 것에 대해 생각해보십시오. 각 항목은 착륙 상자를 선택해야합니다.

첫 번째 항목부터 시작하여 n 개의 가능한 선택 사항이 있습니다. 이제 두 번째 항목이 들어오고 상자 선택도 n 개 있습니다. 항목과 상자는 모두 구별 할 수 있으므로 순열 할인에 대해 걱정할 필요가 없습니다 (일반적으로 구분할 수없는 항목에 대해 수행해야하므로). 이 시점까지 가능한 다른 총 수는 n x n입니다.

세 번째 항목을 가져 오면 n 선택 사항을 가지므로 가능한 총 숫자는 n x n x n입니다.

k 항목이있을 때 대답은 n^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)