정수의 모든 구성을 k 부분으로 생성

Question

K 부분에 정수 N의 모든 구성 (http://en.wikipedia.org/wiki/Composition_%28number_theory%29)을 생성하는 방법을 알 수는 없지만 한 번에 하나씩 만 수행합니다. 즉, 생성 된 이전 컴포지션에서 시퀀스의 다음 컴포지션을 반환하는 함수가 필요합니다. 그 이유는 내 응용 프로그램에 대한 메모리가 제한되어 있기 때문입니다. 파이썬과 그 생성기 기능을 사용할 수 있다면 훨씬 더 쉬워 질 것입니다. 그러나 C++에 익숙해 져 있습니다.

이 어떤 도움을 크게 감상 할 수있다 Next Composition of n into k parts - does anyone have a working algorithm?

유사하다.

Answer 1

당신은 같은 것을 시도해 볼 수도 있습니다 : 배열과

시작 [1,1, ..., 1, N-K + 1] (K-1) 사람의 나머지 1 개 항목. 다음 구성은 (K-1) 번째 요소를 증가시키고 마지막 요소를 감소시킴으로써 생성 될 수 있습니다. 마지막 요소가 두 번째 요소보다 크면이 트릭을 수행하십시오.

마지막 요소가 작아지면 (K-2) 번째 요소를 증가시키고 (K-1) 번째 요소를 같은 값으로 설정하고 마지막 요소를 나머지 값으로 다시 설정하십시오. 이 과정을 반복하고 필요한 경우 다른 요소에 대해 동일한 원리를 적용하십시오.

중복 된 구성을 피하는 끊임없이 정렬 된 배열로 끝납니다.