在java中生成给定集合的nCr组合

Question

我希望java实现生成给定集合的nCr组合。如果设置为{“java”，“php”，“。net”，“python”} 程序应该返回给定集合的所有可能的nCr集合。

Answer 1

适应Gosper's hack，这对于高至N = 64

List<String> inputs; 
List<List<String>> ncr = new ArrayList<List<String>>(); 
for (long x = (1 << r) - 1; (x >>> r) == 0;) { 
    // x contains a 1 bit for each input we should choose; 
    // iterate over the 1 bits of x 
    long y = x; 
    List<String> combination = new ArrayList<String>(); 
    for (int i = Long.numberOfTrailingZeros(y); 
     y != 0; i = Long.numberOfTrailingZeros(y)) { 
    combination.add(inputs.get(i)); 
    y &= ~(1 << i); 
    } 
    long u = x & -x; 
    long v = u + x; 
    x = v + ((v^x)/u) >>> 2; 
}