파이썬 : 주어진 숫자의 가능한 모든 조합 찾기

Question

퍼즐을 풀고 있습니다. 내가 양의 정수를 가지고 있다고 가정 해 봅시다. "8"(양의 정수일 수 있습니다)이라고합시다.

내 정수와 같은 양의 정수를 모두 생성 할 수있는 알고리즘을 만들려면 어떻게해야합니까? 예 :

8 = 7+1 
8 = 6+2 
8 = 6+1+1 
8 = 5+3 
8 = 5+2+1 
8 = 5+1+1+1 
8 = 4+4 
8 = 4+3+1 
8 = 4+2+2 
8 = 4+2+1+1 

등등.

당신은 도움이 코드를 찾을 수 있습니다

Answer 1

:

def sum_to_n(n, size, limit=None): 
    """Produce all lists of `size` positive integers in decreasing order 
    that add up to `n`.""" 
    if size == 1: 
     yield [n] 
     return 
    if limit is None: 
     limit = n 
    start = (n + size - 1) // size 
    stop = min(limit, n - size + 1) + 1 
    for i in range(start, stop): 
     for tail in sum_to_n(n - i, size - 1, i): 
      yield [i] + tail 

for partition in sum_to_n(6, 3): 
    print (partition) 

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

Answer 2

비슷한 질문 :

Algorithm that takes an integer and returns all possible format of addition

자바 구현 링크

ALGORITHM PRACTICE – POSSIBLE ADDITION COMBINATIONS FOR ANY GIVEN NUMBER

Answer 3

놓친 시드-EL에게 추가를 반복 조금 통과 :

def sum_to_n(n, size, limit=None): 
    """Produce all lists of `size` positive integers in decreasing order 
    that add up to `n`.""" 
    if size == 1: 
     yield [n] 
     return 
    if limit is None: 
     limit = n 
    start = (n + size - 1) // size 
    stop = min(limit, n - size + 1) + 1 
    for i in range(start, stop): 
     for tail in sum_to_n(n - i, size - 1, i): 
      yield [i] + tail 

def n_sum(n): 
    ret_list = [] 
    for s in range(1, n): 
     for m in sum_to_n(n, s): 
      ret_list.append(m) 
    ret_list.append([1]*n) 
    return ret_list 

# You would use this as a command: 
>>> n_sum(8) 
[[8], [4, 4], [5, 3], [6, 2], [7, 1], [3, 3, 2], [4, 2, 2], [4, 3, 1], [5, 2, 1], [6, 1, 1], [2, 2, 2, 2], [3, 2, 2, 1], [3, 3, 1, 1], [4, 2, 1, 1], [5, 1, 1, 1], [2, 2, 2, 1, 1], [3, 2, 1, 1, 1], [4, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]]