求组合算法

Question

本帖最后由 JebySin 于 2011-06-24 23:31:35 编辑

Answer 1

想了一下，取组合算法很简单。
设有n个元素，组合数量有2的n次方种。
对 0 到 2的n次方-1 中的每个数，考察其二进制位形式，位数为1代表相应元素加入到组合，0则不加入该元素至组合。
代码如下：
import java.util.ArrayList;
import java.util.List;public class Combinations { /*  取组合方法
 *     参数： list ---- 原始数组
 *     返回：  包含所有组合数组的数组
 */
public static List<List<Object>> getCombinations(List<Object> list) {
List<List<Object>> result = new ArrayList<List<Object>>();
long n = (long)Math.pow(2,list.size());
List<Object> combine;
for (long l=0L; l<n; l++) {
combine = new ArrayList<Object>();
for (int i=0; i<list.size(); i++) {
if ((l>>>i&1) == 1)
combine.add(list.get(i));
}
result.add(combine);
}
return result;
}

//测试
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");
List<List<Object>> result = getCombinations(list);
System.out.println(list.toString());
System.out.println(result.toString());
}}

Answer 2

组合算法，可以采用模拟进制的方式
for exampleString[][] s = {{"a","b"}, {"c", "d", "e"}, {"f", "g"}};
//求s[0],s[1],s[2]中的元素的所有组合void combie(s) {
    int[] dig = new int[s.length]; //用来模拟进位
     Arrays.fill(dig, 0);    while (dig[0] < s[0].length) { //进位最高位不满最大的时候循环
        for (int i=0; i<s.length; i++) {
            System.out.prinf("%s ", s[i][dig[i]]); //打印每个数组的当前进位位置的元素
        }
        System.out.println();        dig[dig.length-1]++; //模拟进位，末位+1
        for (int i=dig.length-1; i>0; i--) {
            if (dig[i] == s[i].length) {  //当某进位位置达到最大时往前进位
                dig[i] = 0; //当前位清0恢复最小状态
                dig[i-1]++; //进位
            } else {
                break; //不满足进位时break
            }
        }
    }
}

Answer 3

if ((l>>>i&1) == 1)  这一句能否解释下，还没用过。

Answer 4

l>>>i&1
l右移i位，再与1进行按位与操作（l>>>i&1） == 1的实际效果为取得l的二进制数的从右往左数第i+1位，判断其是否为1

Answer 5

不知道LZ做的是什么组合？
除了4L说的，多个集合里分别取一个元素进行组合外，一般还有一个集合里取n个元素进行组合，一样也可以采用模拟进位的方式，如String s = {"a", "b", "c", "d", "e"};
//从s里取出n个元素组合void combine(String[] s, int n) {
    int[] dig = new int[s.length]; //进位用数组
    StringBuilder state = new StringBuilder();
    for (int i=s.length-1, j=0; i>=0; i--, j++) { //初始化进位数组状态
        if (s.length-i>n) {                       //如s有5个元素，n为2，即取2个元素组合
            dig[i] = 0;                           //那么初始状态为 00011
        }
        else {
            dig[i] = 1;
        }
        state.append(dig[i]);
    }
    
    String max = state.toString();          //获取进位的最大状态，如上面的假设 11000
    String min = state.reverse().toString();//获取进位的最小状态，即数组初始状态 00011
    while (max.compareTo(min) >= 0) { //当最小状态比不大于最大状态的时候循环
        if (min.length()-min.replaceAll("1", "").length() == n) { //当进位状态中
            for (int i=0; i<s.length; i++) {                      //1的个数为n时打印
                if (dig[i] == 1) {System.out.printf("%s ", s[i]);}
            }
            System.out.println();
        }         dig[dig.length-1]++; //模拟进位，末位+1
        for (int i=dig.length-1; i>0; i--) {
            if (dig[i] == 2) { //当某位进位位置达到最大状态时
                dig[i] = 0; //清0
                dig[i-1]++; //往前进位
            } else {
                break; //不满足进位 break
            }
        }
        
        min = Arrays.toString(dig).replaceAll("\\D+", ""); //重新获得进位状态
    }
}

Answer 6

我的理解，既然LZ提到了与排列对应的组合，他指的应当是概率论中排列与组合的基本概念。即从一个给定的集合中取得所有可能的排列或所有的组合。取元素个数为x的组合是给这个问题加一个约束条件，取得的结果是总结果的一个子集。

Answer 7

如果向做全组合，可以通过一个循环调用
for example
String[] s = {"a", "b", "c", "d", "e"};
for (int i=1; i<=s.length; i++) {
    combine(s, i); //
}
也就是说从集合s里，取1个元素组合，然后再取2个元素组合，然后再3个元素组合，等等，直到n个元素组合，这个n=s的总个数为止就可以了。