整数の固定長パーティションのすべての順列を生成するアルゴリズムを探しています。順序は関係ありません。
たとえば、n=4および長さL=3の場合：
[(0, 2, 2), (2, 0, 2), (2, 2, 0),
(2, 1, 1), (1, 2, 1), (1, 1, 2),
(0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3),
(0, 0, 4), (4, 0, 0), (0, 4, 0)]
私は整数パーティション+長さがLより短いパーティションの順列でぶつかりました。しかし、同じパーティションを複数回取得したため、速度が遅すぎました（;-[0, 0, 1]の順列である可能性がある[0, 0, 1]ため）
どんな助けもありがたいです、そしていいえ、これは宿題ではありません-個人的な興味:-)
わかった。まず、順列を忘れて、長さLのパーティションを生成します（@Svein Bringsliによって提案されたように）。パーティションごとに、>などの要素に順序を付けることができることに注意してください。注文を維持しながら、「カウント」するだけです。n = 4の場合、k = 3：
(4, 0, 0)
(3, 1, 0)
(2, 2, 0)
(2, 1, 1)
では、これをどのように実装するのですか？次のようになります。位置iから1を減算し、それを次の位置に加算すると、順序が維持されます。位置iから1を減算し、位置i + 1に1を加算して、次の位置に移動します。最後の位置にいる場合は、後退します。
これがまさにそれを行う小さなPythonです：
def partition_helper(l, i, result):
if i == len(l) - 1:
return
while l[i] - 1 >= l[i + 1] + 1:
l[i] -= 1
l[i + 1] += 1
result.append(list(l))
partition_helper(l, i + 1, result)
def partition(n, k):
l = [n] + [0] * (k - 1)
result = [list(l)]
partition_helper(l, 0, result)
return result
これでリストのリスト（実際にはマルチセットのリスト）ができました。リストの各マルチセットのすべての順列を生成すると、ソリューションが得られます。これについては説明しません。基本的に、位置ごとにマルチセット内の一意の要素を選択し、その要素をマルチセットから削除した結果のマルチセットの順列を追加する再帰アルゴリズムがあります。
@pbarranisが指摘しているように、 nがkに等しい場合、@rlibbyによるコードにはすべてのリストが含まれるわけではありません。以下は、すべてのリストを含むPythonコードです。このコードは再帰的ではないため、メモリ使用量に関してより効率的である可能性があります。
def successor(n, l):
idx = [j for j in range(len(l)) if l[j] < l[0]-1]
if not idx:
return False
i = idx[0]
l[1:i+1] = [l[i]+1]*(len(l[1:i+1]))
l[0] = n - sum(l[1:])
return True
def partitions(n, k):
l = [0]*k
l[0] = n
results = []
results.append(list(l))
while successor(n, l):
results.append(list(l))
return results
リストは、語彙の順序で作成されます（アルゴリズムと詳細はこちら）。
再帰関数を使用すると、RAMが大量に消費されるため、長さと整数が大きくなると適切ではないことがわかりました。また、ジェネレーター/再開可能関数（「yields」値）の使用は遅すぎて、クロスさせるには大きなライブラリが必要でした。 -プラットホーム。
したがって、これがC ++の非再帰的ソリューションであり、ソートされた順序でパーティションを生成します（これは順列にも理想的です）。これは、パーティションの長さが4以上の場合に試した、一見巧妙で簡潔な再帰的ソリューションよりも10倍以上高速であることがわかりましたが、長さが1〜3の場合、パフォーマンスは必ずしも優れているとは限りません（短いことは気にしません）。どちらのアプローチでも高速であるため、長さ）。
// Inputs
unsigned short myInt = 10;
unsigned short len = 3;
// Partition variables.
vector<unsigned short> partition(len);
unsigned short last = len - 1;
unsigned short penult = last - 1;
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3.
unsigned short sum = 0;
// Prefill partition with 0.
fill(partition.begin(), partition.end(), 0);
do {
// Calculate remainder.
partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints.
/*
*
* DO SOMETHING WITH "partition" HERE.
*
*/
if (partition[cur + 1] <= partition[cur] + 1) {
do {
cur--;
} while (
cur > 0 &&
accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt
);
// Escape if seeked behind too far.
// I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3.
if (cur < 0) {
break;
}
// Increment the new cur position.
sum++;
partition[cur]++;
// The value in each position must be at least as large as the
// value in the previous position.
for (unsigned short i = cur + 1; i < last; ++i) {
sum = sum - partition[i] + partition[i - 1];
partition[i] = partition[i - 1];
}
// Reset cur for next time.
cur = penult;
}
else {
sum++;
partition[penult]++;
}
} while (myInt - sum >= partition[penult]);
私が書いたところは、ここに「パーティション」で何かをします。実際に値を消費する場所です。（最後の反復で、コードはループの残りの部分を実行し続けますが、これは終了条件を常にチェックするよりも優れていることがわかりました-より大きな操作用に最適化されています）
0,0,10 0,1,9 0,2,8 0,3,7 0,4,6 0,5,5 1,1,8 1,2,7 1,3,6 1,4,5 2,2,6 2,3,5 2,4,4 3,3,4
長さと整数が特定の制限を超えないことがわかっているので、「unsigned short」を使用しました。適切でない場合は、変更してください:)コメントを確認してください。そこにある1つの変数（cur）は、1または2の長さを処理するために署名する必要があり、それに対応するifステートメントがあります。また、コメントで、パーティションベクトルがintに署名している場合は、別の行があることにも注意しました。それは単純化することができます。
すべての構成を取得するために、C ++では、この単純な順列戦略を使用します。これは、ありがたいことに重複を生成しません。
do {
// Your code goes here.
} while (next_permutation(partition.begin(), partition.end()));
DO SOMETHING WITH "partition" hereスポットにネストすれば、準備完了です。
構成を見つける代わりに（ここのJavaコードhttps://www.nayuki.io/page/next-lexicographical-permutation-algorithmに基づいて）次のようになります。next_permutation（）よりもパフォーマンスが優れていることがわかりました。
// Process lexicographic permutations of partition (compositions).
composition = partition;
do {
// Your code goes here.
// Find longest non-increasing suffix
i = last;
while (i > 0 && composition[i - 1] >= composition[i]) {
--i;
}
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0) {
break;
}
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
j = last;
while (composition[j] <= composition[i - 1])
--j;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
temp = composition[i - 1];
composition[i - 1] = composition[j];
composition[j] = temp;
// Reverse the suffix
j = last;
while (i < j) {
temp = composition[i];
composition[i] = composition[j];
composition[j] = temp;
++i;
--j;
}
} while (true);
そこにいくつかの宣言されていない変数があります。コードの早い段階で、すべてのdo-loopの前に宣言してください：i、、、、（unsigned shorts）、およびj（posと同じタイプと長さ）。forの宣言は、パーティションコードスニペットのforループで使用するために再利用できます。また、このコードが前述のパーティションコード内にネストされていることを前提とした、使用されているような変数にも注意してください。tempcompositionpartitionilast
繰り返しますが、「あなたのコードはここにあります」は、あなたがあなた自身の目的のために構成を消費する場所です。
参考までに、ここに私のヘッダーがあります。
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;
これらのアプローチを使用すると速度が大幅に向上しますが、かなりの整数とパーティションの長さの場合でも、CPUに腹を立てることになります:)
上で述べたように、@ rlibbyのコードを自分のニーズに合わせて機能させることができず、n = lのコードが必要だったので、ニーズのサブセットにすぎません。これがC＃での以下の私のコードです。上記の質問に対する完全な答えではないことはわかっていますが、lのさまざまな値で機能するようにするには、最初のメソッドを変更するだけでよいと思います。基本的に@rlibbyが行ったのと同じコードを追加し、長さnの代わりに長さlの配列を作成します。
public static List<int[]> GetPartitionPermutations(int n)
{
int[] l = new int[n];
var results = new List<int[]>();
GeneratePermutations(l, n, n, 0, results);
return results;
}
private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results)
{
if (n == 0)
{
for (; i < l.Length; ++i)
{
l[i] = 0;
}
results.Add(l.ToArray());
return;
}
for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt)
{
l[i] = cnt;
GeneratePermutations(l, (n - cnt), cnt, i + 1, results);
}
}
多くの検索がこの質問につながりました。これが順列を含む答えです：
#!/usr/bin/python
from itertools import combinations_with_replacement as cr
def all_partitions(n, k):
"""
Return all possible combinations that add up to n
i.e. divide n objects in k DISTINCT boxes in all possible ways
"""
all_part = []
for div in cr(range(n+1), k-1):
counts = [div[0]]
for i in range(1, k-1):
counts.append(div[i] - div[i-1])
counts.append(n-div[-1])
all_part.append(counts)
return all_part
たとえば、OPによって要求されたall_part（4、3）は、次のようになります。
[[0, 0, 4],
[0, 1, 3],
[0, 2, 2],
[0, 3, 1],
[0, 4, 0],
[1, 0, 3],
[1, 1, 2],
[1, 2, 1],
[1, 3, 0],
[2, 0, 2],
[2, 1, 1],
[2, 2, 0],
[3, 0, 1],
[3, 1, 0],
[4, 0, 0]]