寻找一种非递归算法，以字典顺序访问多重集合的所有k组合。

Question

更具体地说，我正在寻找一种算法A，它的输入为：

• 一个非负整数排序的多重集合M = {a₁, a₂, ..., a_n}；
• 一个整数0 ≤ k ≤ n = |M|；
• 一个“访问者”回调函数V（以M的k组合作为输入）；
• （可选）一个排序的k组合K（默认值：{a₁, a₂, ..., a_k}）。

算法将按字典顺序遍历所有M的k-组合，从K开始，并对每个应用回调函数V。

例如，如果M= {0, 0, 1, 2}，k= 2，K={0, 1}，则执行A(M, k, V, K)将导致以此顺序将访问者回调V应用于每个k-组合{0, 1}，{0, 2}，{1, 2}。 一个重要的要求是该算法是非递归的。

更不重要的是，k组合被访问的确切顺序，只要顺序一致即可。例如，字典序顺序也可以。这个要求的原因是为了能够通过批量运行算法来访问所有k组合。

---

如果我的术语有任何歧义，在本文的其余部分中，我会提供一些定义，希望能澄清问题。

一个多重集合类似于一个集合，但允许重复。例如，M= {0, 0, 1, 2}是一个大小为4的多重集合。对于这个问题，我只关心有限的多重集合。此外，对于这个问题，我假设多重集合的元素都是非负整数。

将多重集合M的大小为k的任意子多重集合定义为k-combination。例如，M= {0, 0, 1, 2}的2-combinations是{0, 0}，{0, 1}，{0, 2}和{1, 2}。

与集合类似，多重集合元素的顺序不重要。（例如，M也可以表示为{2,0,1,0}或{1,2,0,0}等）但是我们可以定义多重集合的规范表示为其中元素（假定为非负整数）按升序排序的表示方式。在这种情况下，多重集合的任何k -组合集合本身都可以通过其成员的规范表示按字典顺序排序。（前面给出的所有M的2-组合序列展示了这样一种排序方式。）

---

更新：下面我尽可能忠实地将 rici的优雅算法从C++翻译成JavaScript，并在其周围包装了一个简单的包装器以符合问题的规范和符号。

function A(M, k, V, K) {

    if (K === undefined) K = M.slice(0, k);

    var less_than = function (a, b) { return a < b; };

    function next_comb(first, last,
                       /* first_value */ _, last_value,
                       comp) {

        if (comp === undefined) comp = less_than;

        // 1. Find the rightmost value which could be advanced, if any
        var p = last;

        while (p != first && ! comp(K[p - 1], M[--last_value])) --p;
        if (p == first) return false;

        // 2. Find the smallest value which is greater than the selected value
        for (--p; comp(K[p], M[last_value - 1]); --last_value) ;

        // 3. Overwrite the suffix of the subset with the lexicographically
        //    smallest sequence starting with the new value
        while (p !== last) K[p++] = M[last_value++];

        return true;
    }

    while (true) {
        V(K);
        if (!next_comb(0, k, 0, M.length)) break;
    }
}

演示：

function print_it (K) { console.log(K); }

A([0, 0, 0, 0, 1, 1, 1, 2, 2, 3], 8, print_it);

// [0, 0, 0, 0, 1, 1, 1, 2]
// [0, 0, 0, 0, 1, 1, 1, 3]
// [0, 0, 0, 0, 1, 1, 2, 2]
// [0, 0, 0, 0, 1, 1, 2, 3]
// [0, 0, 0, 0, 1, 2, 2, 3]
// [0, 0, 0, 1, 1, 1, 2, 2]
// [0, 0, 0, 1, 1, 1, 2, 3]
// [0, 0, 0, 1, 1, 2, 2, 3]
// [0, 0, 1, 1, 1, 2, 2, 3]

A([0, 0, 0, 0, 1, 1, 1, 2, 2, 3], 8, print_it, [0, 0, 0, 0, 1, 2, 2, 3]);

// [0, 0, 0, 0, 1, 2, 2, 3]
// [0, 0, 0, 1, 1, 1, 2, 2]
// [0, 0, 0, 1, 1, 1, 2, 3]
// [0, 0, 0, 1, 1, 2, 2, 3]
// [0, 0, 1, 1, 1, 2, 2, 3]

当然，这不是生产就绪的代码。特别是为了易读性，我省略了所有的错误检查。此外，生产环境中的实现可能会以不同的方式组织事物。(例如，在这里指定由 next_combination 使用的比较器选项将变得多余。) 我的主要目标是在一段可运行的代码中尽可能清晰地保留原始算法背后的思想。

- kjo

---

如果你不介意C++，可以看一下https://dev59.com/u4vda4cB1Zd3GeqPYFY2#30518940。 - rici

@rici：太美了，让我一整天都很开心。我已经将它翻译成JS，并将其作为我的原始帖子的更新添加了进去。我不想把它作为我的答案发布，因为我不想得到这个功劳。你可以自由地将其发布为你的答案，我会接受的。 - kjo

Answer 1

我查看了TAoCP的相关章节，但这个问题在那里最多只是一个练习题。基本思路与算法L相同：先尝试“增加”最不重要的位置，填充成功增量后的位置以其最低允许值。

以下是可能有效但需要更好数据结构的Python代码：

def increment(M, K):
    M = list(M)  # copy them
    K = list(K)
    for x in K:  # compute the difference
        M.remove(x)
    for i in range(len(K) - 1, -1, -1):
        candidates = [x for x in M if x > K[i]]
        if len(candidates) < len(K) - i:
            M.append(K[i])
            continue
        candidates.sort()
        K[i:] = candidates[:len(K) - i]
        return K
    return None


def demo():
    M = [0, 0, 1, 1, 2, 2, 3, 3]
    K = [0, 0, 1]
    while K is not None:
        print(K)
        K = increment(M, K)

- David Eisenstat

Answer 2

在迭代编程中，要生成K个元素的组合，需要使用K个for循环。首先，我们从排序后的输入中删除重复项，然后创建一个表示for循环索引的数组。只要索引数组不溢出，我们就继续生成组合。

adder函数模拟了堆叠的for循环计数器的进度。下面的实现还有一些改进的空间。

N = size of the distinct input
K = pick size
i = 0 To K - 1
for(var v_{i0} = i_{0}; v_{i} < N - (K - (i + 1)); v_{i}++) {
...
for(var v_{iK-1} = i_{K-1}; v_{iK-1} < N - (K - (i + 1)); v_{iK-1}++) {
  combo = [ array[v_{i0}] ... array[v_{iK-1}] ];
}
...
}

这是JavaScript的工作源代码

function adder(arr, max) {
  var k = arr.length;
  var n = max;
  var carry = false;
  var i;
  do {
  for(i = k - 1; i >= 0; i--) {
    arr[i]++;
    if(arr[i] < n - (k - (i + 1))) {
      break;
    }
    carry = true;
  }
  if(carry === true && i < 0) {
    return false; // overflow;
  }
  if(carry === false) { 
    return true;
  }
  carry = false;
  for(i = i + 1; i < k; i++) {
    arr[i] = arr[i - 1] + 1;
    if(arr[i] >= n - (k - (i + 1))) {
      carry = true;
    }
  }
  } while(carry === true);
  return true;
}
function nchoosekUniq(arr, k, cb) {
  // make the array a distinct set
  var set = new Set();
  for(var i=0; i < arr.length; i++) { set.add(arr[i]); }
  arr = [];
  set.forEach(function(v) { arr.push(v); });
  //
  var n = arr.length;
  // create index array
  var iArr = Array(k);
  for(var i=0; i < k; i++) { iArr[i] = i; }
  // find unique combinations;
  do {
    var combo = [];
    for(var i=0; i < iArr.length; i++) {
      combo.push(arr[iArr[i]]);
    }
    cb(combo);
  } while(adder(iArr, n) === true);
}
var arr = [0, 0, 1, 2]; 
var k = 2;
nchoosekUniq(arr, k, function(set) { 
  var s=""; 
  set.forEach(function(v) { s+=v; }); 
  console.log(s); 
}); // 01, 02, 12

- Louis Ricci