実際、この質問は次のように一般化できます。
特定の基準を満たす、特定の要素のセットから可能なすべての組み合わせを検索します。
それで、良いアルゴリズムはありますか？
5996 次
8 に答える
9
可能性は 16 しかありません (そのうちの 1 つは「どれも」を足し合わせるというもので、24 にはなりません)。
for (unsigned int choice = 1; choice < 16; ++choice) {
int sum = 0;
if (choice & 1) sum += elements[0];
if (choice & 2) sum += elements[1];
if (choice & 4) sum += elements[2];
if (choice & 8) sum += elements[3];
if (sum == 24) {
// we have a winner
}
}
問題の完全に一般的な形式では、組み合わせが「特定の基準」を満たしているかどうかを判断する唯一の方法は、すべての組み合わせについてそれらの基準を評価することです。基準に関するより多くの情報があれば、すべての組み合わせをテストすることを回避し、それに応じてアルゴリズムを構築する方法を考え出すことができますが、それらの詳細がなければできません。繰り返しますが、力ずくが王様です。
于 2012-05-16T09:28:46.783 に答える
2
ウィキペディアとMathWorldの両方に、合計の問題に関する 2 つの興味深い説明があります。
あなたが尋ねた最初の質問の場合、最初の答えは限られた数の要素に適しています。ジェソップ氏がループの境界として 16 を使用した理由は、これが 2^4 であるためであることに注意してください。ここで、4 はセット内の要素の数です。100 個の要素がある場合、ループの制限は 2^100 になり、アルゴリズムが完了するまで文字通り永遠にかかります。
制限された合計の場合、深さ優先検索を検討する必要があります。これは、要素の合計が探している合計を超えた場合に、ブランチをプルーニングしてバックトラックできるためです。
一般的な質問の場合、特定の基準を満たす要素のサブセットを見つけることは、NP 完全であることが知られているナップザック問題として知られています。それを考えると、指数時間未満でそれを解決するアルゴリズムはありません。
それにもかかわらず、良い結果をもたらすヒューリスティックがいくつかあります。たとえば、遺伝的アルゴリズム (私が個人的に気に入っているもので、本を書いたことがあります) や動的計画法などです。Google で簡単に検索すると、この問題のさまざまな解決策を説明する多くの科学論文が表示されます。
于 2012-06-04T14:23:45.963 に答える
1
特定の基準を満たす特定の要素のセットから可能なすべての組み合わせを見つける
私があなたを正しく理解していれば、このコードはあなたに役立ちます：
>>> from itertools import combinations as combi
>>> combi.__doc__
'combinations(iterable, r) --> combinations object\n\nReturn successive r-length
combinations of elements in the iterable.\n\ncombinations(range(4), 3) --> (0,1
,2), (0,1,3), (0,2,3), (1,2,3)'
>>> set = range(4)
>>> set
[0, 1, 2, 3]
>>> criteria = range(3)
>>> criteria
[0, 1, 2]
>>> for tuple in list(combi(set, len(criteria))):
... if cmp(list(tuple), criteria) == 0:
... print 'criteria exists in tuple: ', tuple
...
criteria exists in tuple: (0, 1, 2)
>>> list(combi(set, len(criteria)))
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
于 2012-05-16T08:34:21.733 に答える
0
私があなたの質問を正しく理解しているなら、あなたが求めているのは「順列」または（Y）数のセットから取られた（X）数を配置するための可能な方法の数（N）と呼ばれます。
N = Y! / (Y - X)!
これが役立つかどうかはわかりませんが、これは順列の割り当てのために私が思いついた解決策です。
substr関数を使用して：123（文字列）の入力があります
1）入力の各番号を配列に入れます
array[N1,N2,N3,...]
2）スワップ関数を作成する
function swap(Number A, Number B)
{
temp = Number B
Number B = Number A
Number A = temp
}
3）このアルゴリズムは、スワップ関数を使用して、すべての順列が完了するまで数値を移動します。
original_string= '123'
temp_string=''
While( temp_string != original_string)
{
swap(array element[i], array element[i+1])
if (i == 1)
i == 0
temp_string = array.toString
i++
}
うまくいけば、私の擬似コードに従うことができますが、これは少なくとも3桁の順列で機能します
于 2012-06-05T01:49:23.490 に答える
0
一般に、このような問題については、すべてのポーズ能力を試す必要があります。基準を満たさないことがわかっている場合は、コードでコンビネーションの構築を中止する必要があります (基準が 2 つ以上の青いボールを持っていない場合)。の場合、2 つ以上の計算を中止する必要があります)。バックトレース
def perm(set,permutation):
if lenght(set) == lenght(permutation):
print permutation
else:
for element in set:
if permutation.add(element) == criteria:
perm(sett,permutation)
else:
permutation.pop() //remove the element added in the if
于 2012-05-30T15:33:57.110 に答える
0
(n X n ) nxn の正方行列を構築
対応する交差値をすべて一緒に出力します
例えば
1 2 3 4
1 11 12 13 14
2 .. .. .. ..
3 ..
4 .. ..
于 2012-06-05T02:46:28.893 に答える
0
private int[][] work()
{
const int target = 24;
List<int[]> combos = new List<int[]>();
for(int i = 0; i < 9; i++)
for(int x = 0; x < 9; x++)
for(int y = 0; y < 9; y++)
for (int z = 0; z < 9; z++)
{
int res = x + y + z + i;
if (res == target)
{
combos.Add(new int[] { x, y, z, i });
}
}
return combos.ToArray();
}
すぐに機能しますが、おそらく「推測して確認する」よりも優れた方法があります。私がしているのは、すべての可能性をループし、それらをすべて足し合わせて、目標値になるかどうかを確認することだけです.
于 2012-06-04T23:58:03.113 に答える
0
開始セットで負の数、虚数、有理数などを許可するとすぐにわかるように、入力数値のセットは重要です。たとえば、すべての偶数、すべての奇数の入力などに制限することもできます。
つまり、演繹的なものを構築するのは難しいということです。総当たりが必要です。別名、すべての組み合わせを試してください。
この特定の問題では、再帰するアルゴリズムを構築できます。たとえば、3 Int ( 1,22) のすべての組み合わせを見つけて合計 23 にし、次に 1 を追加し、合計 22 と 2 を追加するすべての組み合わせなどを見つけます。これも壊れる可能性があります。合計すると 21 などになる 2 のすべての組み合わせに。同じ数を 2 回数えることができるかどうかを判断する必要があります。
それができたら、呼び出す再帰関数があります-
combinations( 24 , 4 ) = combinations( 23, 3 ) + combinations( 22, 3 ) + ... combinations( 4, 3 );
combinations( 23 , 3 ) = combinations( 22, 2 ) + ... combinations( 3, 2 );
等
これは、再帰での数値の繰り返しに注意する必要があることを除けば、うまく機能します。
于 2012-06-04T21:54:44.840 に答える