자바에서 주어진 세트의 nCr 조합 생성하기

Question

주어진 세트의 nCr 조합을 생성하는 Java 구현이 필요합니다. 예 : set이 { "java", "php", ". net", "python"} 인 경우 프로그램은 주어진 세트의 가능한 모든 nCr 세트를 반환해야합니다. Gosper's hack을 적응

Answer 1

, 이것은 최대 작동에 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; 
}