정수 n을 m 개의 정수의 합계 (순서없이)로 얻는 모든 방법을 찾는 방법은 무엇입니까?

Question

나는 정수 n을 m (음수가 아닌) 정수의 합으로 표현하는 모든 방법을 찾는 알고리즘을 찾고있다. 저는 특히 m = 6과 n⩽20에 관심이 있습니다. 가능한 모든 것을 찾을 수있는 가장 빠른 방법은 무엇입니까? (컴퓨터가 아니라 손으로). 가능한 경우, 관련이없는 순서 (즉, [1, 2, 0, 0, 0, 0] 및 [2, 1, 0, 0, 0, 0)만으로 6 개의 정수 조합을보고 싶습니다. ]은 1 조합으로 계산됩니다).

가장 간단한 방법은 6 이하의 정수를 20보다 작거나 같은 모든 순열을 시도하고 20까지 합계 한 값을 우리 결과에 더하는 것입니다. (우리가 순서를보고 싶지 않으면 두 배를 제거합니다). 이것은 20^6 가능성이 확인하는 데 꽤 오랜 시간이 걸리기 때문에 시간이 많이 걸릴 것 같습니다.

이 문제를 해결하는보다 효율적인 방법은 무엇입니까?

Answer 1

숫자가 단조롭게 증가하는 순서로 숫자를 생성함으로써 반복을 피할 수 있습니다 (각 숫자는 이전 숫자보다 크거나 같음).

주어진 count (예 : 6)의 경우 첫 번째 숫자에 대해 가능한 모든 값을 생성 한 다음 원래의 합계에서 첫 번째 숫자를 뺀 값인 count - 1 숫자의 모든 목록을 재귀 적으로 생성하여 문제를 재귀 적으로 정의 할 수 있습니다. 첫 번째 숫자는 목록의 나머지 숫자에 대한 최소값입니다.

숫자가 증가해야하기 때문에 "너무 일찍 계산할 수 없습니다"- 합계를 개수로 나눔으로써 최대 값을 계산할 수 있습니다 (나머지 값은 모두이 값 이상이어야합니다).).

public static void outputSums(String start, int sum, int count, int min) 
{ 
    // if there is just one value, it's just the sum: 
    if(count == 1) 
    { 
     System.out.println(start + " " + sum); 
     return; 
    } 

    int max = sum/count; // calculate maximum value 
    for(int i = min; i <= max; i++) 
    { 
     outputSums(start + " " + i, // append each number to the list 
      sum - i, // recursively find numbers that sum to the remainder 
      count - 1, // with a count of one less 
      i); // equal to or greater to this one (i.e. increasing order) 
    } 
} 

start는 지금까지 출력이 부분 목록이 포함되어 있습니다 :

여기에 자바 간단한 구현입니다. 처음 함수를 호출하면 비어 있습니다.

Demo

Answer 2

이전 방식의 반대의 가장 큰에서 최소로 계산하는 것입니다.

여기에는 반복기를 사용하여 프로그래밍 방식으로 사용하기가 쉬운 Python 구현이 있습니다. 여기

def partition (count, total, maximum = None) : 
    if maximum is None or total < maximum: 
     maximum = total 
    if 0 == count: 
     yield [] 
    else: 
     while total <= count * maximum: 
      for part in partition(count - 1, total - maximum, maximum): 
       yield part + [maximum] 
      maximum = maximum - 1 

그리고

은 출력을 인쇄하는 프로그램을 사용하는 방법의 예입니다

for part in partition(6, 10): 
    print(part)