生成一个整数的所有组成k部分

Question

我不知道如何生成一个整数N到K部分的所有组成（http://en.wikipedia.org/wiki/Composition_%28number_theory%29），但一次只做一个。也就是说，我需要一个给定先前组合生成的函数，并返回序列中的下一个。原因是内存对于我的应用程序是有限的。如果我可以使用Python及其生成器功能，这将会容易得多，但我坚持使用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）个元素设置为相同的值，并将最后一个元素再次设置为余数。重复该过程并在必要时对其他元素应用相同的原则。

你最终得到一个不断排序的数组，避免重复组合