3

我有一组 x 字符串项，例如（“A”，“B”，“C”，“D”，“E”，“F”）我需要知道计算 n 项组合的数量以及什么的公式是生成所有可能组合的算法，例如，如果我们需要从列表中随机选择 4 个项目。这 4 个项目可能是：("A","B","C","D") 或 ("A","B","C","E") 或 ("A","B" ,"C","F") 或 ("A","B","D","E") ...等我需要计算在不重复的情况下将生成多少组项目的公式，即我们考虑 ("A","B","C","D" ) 作为结果组合之一，我们不能将相同的项目视为另一个结果组合，并替换集合中项目的位置，例如 ("A","B","D","C") 我还需要算法以任何编程语言生成所有可能的组合。[C#,VB.NET,Java,C++]

感谢您的任何帮助。

4

7 回答 7

11

从 n 个项目中选择 p 个，这就是告诉你有多少组合的公式。

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

谷歌计算器将为您计算：

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 选择 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 中的单行解决方案：

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

您需要二项式定理，并且需要嵌套循环。至于您的一种编程语言的实现，编写起来并不难。如果您环顾四周，您会发现这个问题经常在 SO 上被问到，并且您会发现人们因此投票结束您的问题。

于 2010-04-15T06:34:15.333 回答
0

您也可以使用Lexicographic ordering。

像这样的东西：

#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 回答