生成一個整數的所有組成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）個元素設置爲相同的值，並將最後一個元素再次設置爲餘數。重複該過程並在必要時對其他元素應用相同的原則。

你最終得到一個不斷排序的數組，避免重複組合