从一组x项中随机选择的n项的所有可能组合(算法)

Question

我有一组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++]

感谢您的任何帮助.

Answer 1

选择n个项目中的p,这是告诉你有多少组合的公式.

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

Google计算器会为您做数学计算:

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

6选择4 = 15

Answer 2

你所描述的组合公式在@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;
}

所以,如果你想要所有可能的字母组合"ABCDEF",你选择4个字母,那就是c(6,4).