1

Mサイズとの行列が与えられた場合、N合計が特定の値になるように、各行に整数値 (>=0) を入力します。

と の次元は、特定の式を使用して事前に計算されていることに注意してくださいM。Nこれにより、目的の条件 (つまり、以下の sum_val) が与えられた場合に塗りつぶしに一致することが保証されます。

これは R のPartition libraryの下に実装されています。

library(partitions)

# In this example, we impose condition 
# that each rows must sum up to 2 in total
# And each row has 5 columns
sum_val <- 2
n <- 5
#The above two parameters are predefined.

t(as.matrix(compositions(sum_val, n)))
      [,1] [,2] [,3] [,4] [,5]
 [1,]    2    0    0    0    0
 [2,]    1    1    0    0    0
 [3,]    0    2    0    0    0
 [4,]    1    0    1    0    0
 [5,]    0    1    1    0    0
 [6,]    0    0    2    0    0
 [7,]    1    0    0    1    0
 [8,]    0    1    0    1    0
 [9,]    0    0    1    1    0
[10,]    0    0    0    2    0
[11,]    1    0    0    0    1
[12,]    0    1    0    0    1
[13,]    0    0    1    0    1
[14,]    0    0    0    1    1
[15,]    0    0    0    0    2

C++ に既存の実装はありますか?

4

2 に答える 2

2

再帰バージョン

これが再帰的な解決策です。aすでに設定した数値を追跡するシーケンスがあります。各再帰呼び出しは、リストの残りの関数を再帰的に呼び出す前に、ループ内のこれらの要素の 1 つに有効な数値を割り当てます。

void recurse(std::vector<int>& a, int pos, int remaining) {
  if (remaining == 0) { print(a); return; }
  if (pos == a.size()) { return; }
  for (int i = remaining; i >= 0; --i) {
    a[pos] = i;
    recurse(a, pos + 1, remaining - i);
  }
}

void print_partitions(int sum_val, int n) {
  std::vector<int> a(n);
  recurse(a, 0, sum_val);
}

概念実証はhttp://ideone.com/oJNvmuで確認できます。

反復版

以下のコメントは、パフォーマンスの問題を示しています。I/O がパフォーマンスのほとんどを消費している可能性が非常に高いようですが、再帰的アプローチの関数呼び出しのオーバーヘッドを回避する反復ソリューションを次に示します。

void print_partitions(int sum_val, int n) {
  int pos = 0, last = n - 1;
  int a[n]; // dynamic stack-allocated arrays are a gcc extension
  for (int i = 1; i != n; ++i)
    a[i] = 0;
  a[0] = sum_val;
  while (true) {
    for (int i = 0; i != last; ++i)
        printf("%3d ", a[i]);
    printf("%3d\n", a[last]);
    if (pos != last) {
      --a[pos];
      ++pos;
      a[pos] = 1;
    }
    else {
      if (a[last] == sum_val)
        return;
      for (--pos; a[pos] == 0; --pos);
      --a[pos];
      int tmp = 1 + a[last];
      ++pos;
      a[last] = 0;
      a[pos] = tmp;
    }
  }
}

一般的な考え方と印刷される順序は、再帰的アプローチと同じです。counter を維持する代わりにremaining、すべてのトークン (またはパーティション分割しているものは何でも) は、次のパーティションが出力されるために、それらが属する場所にすぐにドロップされます。pos常にゼロ以外の最後のフィールドです。それが最後でない場合は、トークンを 1 つ取得して次posの場所に移動することで、次のパーティションを取得します。それが最後の場合は、その最後の場所からすべてのトークンを取得し、その前のゼロ以外の最後の場所を見つけて、そこからも 1 つのトークンを取得し、これらのトークンをすべて、シングルを取った場所の後の場所にダンプします。トークン。

デモはhttp://ideone.com/N3lSbQで実行されます。

于 2013-07-04T07:05:59.150 に答える