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

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
                            
                        
                    
                
                7年前关闭。
            
        

我想要生成给定集合的nCr组合的Java实现。
例如，如果set为{“ java”，“ php”，“。net”，“ python”}
程序应返回给定集合的所有可能的nCr集。

最佳答案

适应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;
}