0

整数 N のすべての構成 ( http://en.wikipedia.org/wiki/Composition_%28number_theory%29 ) を K 部分に生成する方法がわかりませんが、一度に 1 つずつしか実行できません。つまり、生成された前のコンポジションを指定して、シーケンス内の次のコンポジションを返す関数が必要です。その理由は、アプリケーションのメモリが限られているためです。Python とそのジェネレーター機能を使用できれば、これははるかに簡単になりますが、私は C++ にこだわっています。

これは次の n の k 部分への合成に似ています - 動作するアルゴリズムを持っている人はいますか?

どんな援助でも大歓迎です。

4

2 に答える 2

1

次のようなことを試すことができます：

(K-1) 個の配列 [1,1,...,1,N-k+1] と残りの 1 つのエントリから始めます。次の構成は、(K-1) 番目の要素をインクリメントし、最後の要素を減らすことによって作成できます。最後の要素が 2 番目の要素よりも大きい限り、このトリックを実行します。

最後の要素が小さくなったら、(K-2) 番目の要素をインクリメントし、(K-1) 番目の要素を同じ値に設定し、最後の要素に剰余を再度設定します。このプロセスを繰り返し、必要に応じて他の要素にも同じ原則を適用します。

重複した構成を回避する、常にソートされた配列になります

于 2013-03-23T10:03:40.110 に答える