[PYTHON] 숫자에 합쳐지는 모든 숫자 얻기

숫자에 합쳐지는 모든 숫자 얻기

주어진 정수까지 합쳐진 X 정수의 가능한 모든 집합을 표시하는 방법을 찾으려고합니다. 예를 들어 5를 만들 수있는 2 개의 정수 세트를 모두 얻으려면 :

1, 4
2, 3

또는 6을 만드는 3 개의 정수 :

1, 1, 4
1, 2, 3
2, 2, 2

0을 포함하지 않는 정수 만 필요하며 최대 15 개까지 설정할 수 있습니다. 번호.

이 용어가 수학적으로 사용되는지 확실하지 않습니다. 내가 생각한 인수 분해와 비슷합니까?

해결법

1. ==============================

   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]
   

2. ==============================

   2.http://en.wikipedia.org/wiki/Partition_(number_theory)

   http://en.wikipedia.org/wiki/Partition_(number_theory)

   http://mathworld.wolfram.com/Partition.html

   http://code.activestate.com/recipes/218332/

3. ==============================

   3.여기에 발췌 문장이 있습니다.

   여기에 발췌 문장이 있습니다.

   from itertools import combinations, chain
   
   def sum_to_n(n):
       'Generate the series of +ve integer lists which sum to a +ve integer, n.'
       from operator import sub
       b, mid, e = [0], list(range(1, n)), [n]
       splits = (d for i in range(n) for d in combinations(mid, i)) 
       return (list(map(sub, chain(s, e), chain(b, s))) for s in splits)
   

   다음과 같이 사용하십시오.

   for p in sum_to_n(4):    
       print p
   

   출력 :

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

4. ==============================

   4.이것들은 문제의 정수의 파티션이라고 불린다. 다른 사람들은 그들을 정의하는 링크를 제공했습니다.

   이것들은 문제의 정수의 파티션이라고 불린다. 다른 사람들은 그들을 정의하는 링크를 제공했습니다.

   이러한 일을하는 속임수는 종종 재귀 적으로 수행하는 것입니다. 예를 들어, 10을 정확히 3 개의 정수의 합으로 만드는 모든 별개의 방법을 만들고 싶다고 가정하십시오. 그 중 아무 것도 두 번 이상 나타나지 않습니다.

   그 합계에서 가능한 가장 큰 구성 요소를보십시오. 10이 될 수 있을까요? 아니요, 가장 큰 구성 요소가 10 일 경우 이후 남은 것은 무엇입니까? 즉, 10 - 10 = 0입니다. 합계에서 가장 큰 요소가 7이면 두 개의 양의 정수 합으로 나눌 수있는 값이 3 인 것으로 나타났습니다. 그리고 3을 2의 합으로 나눌 수 있습니다. 정확히 하나의 방식으로 뚜렷한 정수를 구하십시오. 따라서 {7,2,1}은 그러한 파티션이고 7만큼 큰 요소를 포함하는 유일한 파티션입니다.

   6을 가장 큰 요소로 사용할 수 있습니까? 그렇다면 우리는 4 명 남았습니다. 그리고 정확히 4 방향으로 나누어 {6,3,1} 파티션을 만들 수 있습니다. 추가 검색은 {5,4,1}, {5,3,2}와 같이 10의 다른 파티션을 생성합니다. 다른 어떤 것도 존재할 수 없다.

   요컨대,이 연산은 재귀 함수로 쉽게 정의 될 수 있습니다. 신중한 코딩으로, 이전에 보았던 것을 다시 계산하는 것을 피하기 위해 메모 화를 사용할 수도 있습니다.

5. ==============================

   5.귀하의 질문은 다음과 같이 재 설명 할 수 있습니다 :

   귀하의 질문은 다음과 같이 재 설명 할 수 있습니다 :

   먼저 L = 2의 경우를 생각해 봅시다. 이것은 다음 집합을 가질 수 있음을 의미합니다.

   (9,1) , (8,2), (7,3) , (6,4) , (5,5)

   이것을 기본 솔루션이라고 부르면 곧 이유를 알 수 있습니다.

   L을 3으로 변경하고 답을 다시 해봅시다.

   그러면 9를 생각해 봅시다. 합계 (L) + 9 = 10과 같은 그러한 목록 L이 있습니까? 분명한 대답은 아니요.하지만 여기서 흥미로운 점은 대답이 아니라 질문 자체입니다. 우리는 기본적으로 숫자 1로 합계 할 수있는 2 가지 요소 집합을 요구하고 있습니다. 이는 기본 솔루션으로 해결 된 동일한 문제입니다.

   따라서 [9,8,7,6,5,4,3,2,1]의 각 숫자 x에 대해 x + a + b = 10과 같은 집합 [a, b]를 찾으십시오.

   이것은 완전한 대답은 아니지만 아이디어는 여기에 패턴을보고 재귀를 사용하여 위에서 설명한대로 기본 케이스를 계산 한 다음 솔루션을 완료 할 재귀 호출을 파악하는 것입니다. 행운을 빕니다!

from https://stackoverflow.com/questions/2065553/get-all-numbers-that-add-up-to-a-number by cc-by-sa and MIT license