java - 选择元素的所有组合

Question

有一个列表 MyOption元素:

class MyOption{
   List<Integer> listElements;
}

然后我有两个值 allElements和 selectedElements .第一个是 listElements 的大小第二个表示有多少列表项的值为 0(其他为空)。我必须得到 List<MyOption>其中 notnull 元素的每个组合。我知道总有

( allElements! / (selectedElements! * (allElements - selectedElements)! )组合。

例如，对于 allElements=3和 selectedElements=1有: 3!/(1!*(3-1))! = 3组合(listElements 的尺寸为 3，List<MyOption> 的尺寸也为 3):

0      null   null
null     0    null
null   null    0

和 allElements=4 的第二个例子和 selectedElements=2 ，有6种组合:

0      0     null  null
0     null    0    null
0     null   null   0
null   0      0    null
null   0     null   0
null  null    0     0

当我知道 allElements 时，怎么可能得到所有这些？和 selectedElements ？

Answer 1

有一个recursive definition为您的问题提供解决方案的二项式系数:

public static long choose(long allElements, long selectedElements){
    if(allElements < selectedElements)
        return 0;
    if(selectedElements == 0 || selectedElements == allElements)
        return 1;
    return choose(allElements-1,selectedElements-1)+choose(allElements-1,selectedElements);
}

注意:这是一种易于理解的方法，适用于小输入，还有更高效的实现。