3

x 個の文字列アイテムのセットを持っています。eg("A","B","C","D","E","F")リストから 4 つの項目をランダムに選択する必要がある場合など、考えられるすべての組み合わせを生成するアルゴリズムです。これらの 4 つの項目は、("A","B","C","D") または ("A","B","C","E") または ("A","B") のいずれかです。 ,"C","F") または ("A","B","D","E") ...etc 繰り返しなしで生成されるアイテムのセット数を計算する式が必要です。 ("A"、"B"、"C"、"D" ）結果の組み合わせの1つとして、（「A」、「B」、「D」、「C」）のようにセット内のアイテムの位置を置き換えることで、同じアイテムを別の結果の組み合わせと見なすことはできません。また、アルゴリズムが必要です任意のプログラミング言語で可能なすべての組み合わせを生成します。[C#、VB.NET、Java、C++]

助けてくれてありがとう。

4

7 に答える 7

11

n 個のアイテムから p 個を選択すると、これがいくつの組み合わせがあるかを示す公式です。

                  n!
n choose p  = -----------
               p! (n-p)!

Google 電卓が計算してくれます。

http://www.google.com/search?q=6+choose+4

6 選択 4 = 15

于 2010-04-15T06:34:13.653 に答える
5

@Mark Harrison の回答には、あなたが説明する組み合わせの式が示されています。ただし、この方程式を差し込むと爆発します。これは、数学が相殺することが意図されているためです。

たとえば、50 は 49 を選択します。これは、除外する要素を選択することと同じであるため、50 の選択肢があります。ただし、この式では計算する必要があります

   50!       3.04140932e64
-------- = ----------------- = 50
1! * 49!   1 * 6.08281864e62

x choose y に対して「本当に」必要な方程式は次のとおりです。

x * (x-1) * ... * (x-n+1)
-------------------------
n * (n-1) * ... * 2 * 1

いくつかの簡単な C コード [これは、C(x,y) = C(x,xy) を最適化することに注意してください。これは、組み合わせ式から簡単に確認できるはずです]:

int c(int x, int y)
{
    int num = 1, denom = 1;
    int i;
    if (y > x-y)
        y = x - y;
    for (i = 0; i < y; ++i)
    {
        num *= (x - i);
        denom *= (y - i);
    }
    return num/denom;
}

したがって、4 つの文字を選択する文字 "ABCDEF" のすべての可能な組み合わせが必要な場合、つまりc(6,4).

于 2010-04-15T07:28:25.987 に答える
3

どのプログラミング言語でも可能なすべての組み合わせを生成するアルゴリズムが必要です。

さて、Haskell での 1 行のソリューションは次のとおりです。

import Data.List (subsequences)

n `outOf` xs = filter ((n ==) . length) (subsequences xs)

test = 4 `outOf` ["A", "B", "C", "D", "E", "F"]

*Main> test
[["A","B","C","D"],["A","B","C","E"],["A","B","D","E"],["A","C","D","E"],["B","C
","D","E"],["A","B","C","F"],["A","B","D","F"],["A","C","D","F"],["B","C","D","F
"],["A","B","E","F"],["A","C","E","F"],["B","C","E","F"],["A","D","E","F"],["B",
"D","E","F"],["C","D","E","F"]]
*Main> length test
15
于 2010-04-15T12:01:31.867 に答える
1

二項定理が必要で、ネストされたループが必要です。プログラミング言語の 1 つでの実装に関しては、書くのはそれほど難しくありません。周りを見回すと、この質問が SO で定期的に尋ねられていることがわかり、その理由で質問を閉じるために投票する人がいることがわかります。

于 2010-04-15T06:34:15.333 に答える
0

辞書式順序付けもできます。

このようなもの：

#include <stdio.h>

void print(const int *v, const int size)
{
    int i;
    if (v != 0) {
        for (i = 0; i < size; i++) {
            printf("%4d", v[i] );
        }
        printf("\n");
    }
} // print


void visit(int *Value, int N, int k)
{
    int i;
    static level = -1;
    level = level+1; Value[k] = level;

    if (level == N)
        print(Value, N);
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0)
                visit(Value, N, i);

    level = level-1; Value[k] = 0;
}


main()
{
    const int N = 4;
    int Value[N];
    int i;
    for (i = 0; i < N; i++) {
        Value[i] = 0;
    }
    visit(Value, N, 0);
}
于 2010-04-15T06:38:26.787 に答える
0

パスカルの三角形を使用して、組み合わせの数を計算できます。実際の組み合わせを見つけるには、単純な再帰を使用できます。

于 2010-04-15T06:38:50.873 に答える
0

ええ、パスカルの三角形は機能します。


int dp[MAX_X][MAX_Y] = {0};

dp[0][0] = 1;
for (int i = 1; i <= X; i++) {
    dp[i][0] = dp[i][i] = 0;
    for (int j = 1; j < min(i, Y + 1); j++)
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}

print(dp[X][Y])

または、スライディング ウィンドウ トリックを使用して何かを行うこともできます。

もう一度言いますが、値が大きくなりすぎない限り、式はうまく機能すると思います。

于 2010-04-19T02:21:25.713 に答える