java - 使用字典顺序和按位算法顺序生成有限集的所有组合

Question

考虑以下整数数组 {1,2,3} 的所有长度为 3 的组合。

我想使用来自 wikipedia 的以下算法遍历所有长度为 3 的组合

// find next k-combination    
bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
{
  unsigned long u = x & -x; // extract rightmost bit 1; u =  0'00^a10^b
  unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
  if (v==0) // then overflow in v, or x==0
    return false; // signal that next k-combination cannot be represented
  x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
  return true; // successful completion
}

对于 {1,2,3} 的所有组合，此算法的起始值应该是多少？ 当我得到算法的输出时，如何恢复组合？

我尝试了以下直接改编，但我是按位算术的新手，我不知道这是否正确。

// find next k-combination, Java    
int next_combination(int x)
{
  int u = x & -x; 
  int v = u + x; 
  if (v==0) 
    return v; 
  x = v +(((v^x)/u)>>2); 
  return x; 
}

Answer 1

我找到了一个类，正好解决了这个问题。在此处查看类 CombinationGenerator

https://bitbucket.org/rayortigas/everyhand-java/src/9e5f1d7bd9ca/src/Combinatorics.java

要恢复组合，请执行

for(Long combination : combinationIterator(10,3))       
    toCombination(toPermutation(combination);

感谢大家的意见。