生成长度为 n 的子集 [英] Generate subsets of length n

问题描述

给定一个 Set，生成所有长度为 n 的子集.

Given a Set, generate all subsets of length n.

• 样本输入:

• Sample input:

set = new Set(['a', 'b', 'c']), length = 2

示例输出:

Sample output:

Set {'a', 'b'}, Set {'a', 'c'}, Set {'b', 'c'}

如何在不将 Set 转换为 Array 的情况下有效地做到这一点?

How to do this efficiently, without converting the Set to an Array?

我已经有一个很好的数组作为输入的解决方案:

I already have a good solution for arrays as input:

function* subsets(array, length, start = 0) {
  if (start >= array.length || length < 1) {
    yield new Set();
  } else {
    while (start <= array.length - length) {
      let first = array[start];
      for (subset of subsets(array, length - 1, start + 1)) {
        subset.add(first);
        yield subset;
      }
      ++start;
    }
  }
}

let array = ['a', 'b', 'c', 'd'];

for (subset of subsets(array, 2)) {
  console.log(...subset);
}

但是，如果不将集合转换为数组，我无法为集合提出有效的实现 - 我想避免使用例如纯粹使用迭代器.

However, I couldn't come up with an efficient implementation for sets without converting the set to an array - wich I would like to avoid in favour of e.g. purely using iterators.

推荐答案

我实现了您使用有序多子集删除和重新插入值的想法:

I implemented your idea of deleting and reinserting values with ordered multi subsets:

function orderedMultiSubsets(set, n) {
  if(!Number.isInteger(n) || n < 0) return function*(){}();
  var subset = new Array(n),
      iterator = set.values();
  return (function* backtrack(index) {
    if(index === n) {
      yield subset.slice();
    } else {
      for(var i=0; i<set.size; ++i) {
        subset[index] = iterator.next().value; /* Get first item */
        set.delete(subset[index]); /* Remove it */
        set.add(subset[index]); /* Insert it at the end */
        yield* backtrack(index+1);
      }
    }
  })(0);
}
for(var subset of orderedMultiSubsets(new Set([1,2,3]), 2)) {
  console.log(subset.join());
}

然后我想我设法尽早为无序子集情况修剪:

And then I think I managed to prune as early as possible for the unordered subsets case:

function subsets(set, n) {
  if(!Number.isInteger(n) || n < 0 || n > set.size) return function*(){}();
  var subset = new Array(n),
      iterator = set.values();
  return (function* backtrack(index, remaining) {
    if(index === n) {
      yield subset.slice();
    } else {
      for(var i=0; i<set.size; ++i) {
        subset[index] = iterator.next().value; /* Get first item */
        set.delete(subset[index]); /* Remove it */
        set.add(subset[index]); /* Insert it at the end */
        if(i <= remaining) {
          yield* backtrack(index+1, remaining-i);
        }
      }
    }
  })(0, set.size-n);
}
for(var subset of subsets(new Set([1,2,3,4]), 2)) {
  console.log(subset.join());
}

我仍然使用数组作为子集，但它的大小仅为 n.因此，如果集合的大小比 n 大得多，这种方法可能比将集合复制到数组中使用更少的内存，我想这就是您的问题所在.但请注意，删除和插入可能比数组查找更昂贵.

I still use an array for the subsets, but its size is only n. So in case the size of the set is much bigger than n, this approach might use less memory than duplicating the set into an array, which I guess is the point of your question. But note that the deletions and insertions are probably more expensive than array lookups.

奖励:最后，集合的顺序和调用函数之前一样.

Bonus: at the end, the order of the set is the same as before calling the function.

这篇关于生成长度为 n 的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！