寻找一种非递归算法，用于按字典顺序访问多集的所有k个组合

更具体地说，我正在寻找一个算法A，将其作为输入

M , =, {<子> 1 ,<子> 2 ,白马王子;,,<子> n ,}的非负整数,
一个整数0,&leq;, k , &leq;, n , =, | M , |;
一个"访客"回调V(取k- M的组合作为输入);

算法将按照字典顺序访问M的所有k组合，从k开始，并对每个V应用回调。

为例,如果 M , =, {0, 0, 1,, 2}, k , =, 2,和k , =,{0, 1},然后执行 ( M , k , V , k ,)会导致游客的应用回调V 的 k 组合{0,1},{0,,2},{1,,2},在这个秩序。

一个关键的要求是算法是非递归的

不那么重要的是访问k组合的精确顺序，只要顺序一致。例如，colexicographic顺序也可以。此要求的原因是能够通过批量运行算法来访问所有k组合。

如果在我的术语中有任何歧义，在这篇文章的其余部分，我给出了一些定义，我希望能澄清问题。

一个multiset类似于一个集合，只是允许重复。例如，M = {0， 0， 1， 2}是一个大小为4的多集。对于这个问题，我只对有限多集感兴趣。同样，对于这个问题，我假定多集合的元素都是非负整数。

定义multiset M的k-combination作为大小为k的M的任意子multiset。如 M的2-combinations , =,{0, 0, 1,, 2}{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 's使用的比较器的选项在这里变得多余。)我的主要目的是在一段功能代码中尽可能清晰地保留原始算法背后的思想。

我查看了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)

在迭代编程中，要生成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

相关内容

最新更新

热门标签：