在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; 
}