给定一个数组，如何生成子集大小为 k 的所有组合？

Question

所以给定 input = [1, 2, 3] 和 k=2 这将 return:

这是最接近我所寻找的，但不完全是：http://algorithms.tutorialhorizon.com/print-all-combinations-of-subset-of-size-k-from-given-array/

function subsetsOfSize(a, used, startIndex, currentSize, k) {
  if (currentSize === k) {
    for (var i = 0; i < a.length; i++) {
      if (used[i])
        console.log(a[i]);
    }
    console.log('-');
    return;
  }
    
  if (startIndex === a.length)
    return;
    
  used[startIndex] = true;
  subsetsOfSize(a, used, startIndex+1, currentSize+1, k);

  used[startIndex] = false;
  subsetsOfSize(a, used, startIndex+1, currentSize, k);
}

var input = [1,2,3];
subsetsOfSize(input, Array(input.length).fill(false), 0, 0, 2);

^ 缺少 2 1、3 1、3 2 等结果

其次，我不确定我是否正确命名了这个问题，因为 "all combinations of subset of size k" 的解决方案没有给出预期的答案。

Answer 1

尝试排列。

而不是组合

尝试生成排列，然后调整数组大小。

这是实现的，修改自here

var permArr = [],
  usedChars = [];

function permute(input, k) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      var toadd = usedChars.slice(0,k);
      if(!permArr.includes(toadd)) permArr.push(toadd); // resizing the returned array to size k
    }
    permute(input, k);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};
console.log(JSON.stringify(permute([1, 2, 3], 2)));

Answer 2

查找 k 子集排列的递归解决方案（伪代码）：

kSubsetPermutations(partial, set, k) {
    for (each element in set) {
        if (k equals 1) {
            store partial + element
        }
        else {
            make copy of set
            remove element from copy of set
            recurse with (partial + element, copy of set, k - 1)
        }
    }
}

这里有一个运行-through 的例子：

input: [a,b,c,d,e]
k: 3

partial = [], set = [a,b,c,d,e], k = 3
    partial = [a], set = [b,c,d,e], k = 2
        partial = [a,b], set = [c,d,e], k = 1 -> [a,b,c], [a,b,d], [a,b,e]
        partial = [a,c], set = [b,d,e], k = 1 -> [a,c,b], [a,c,d], [a,c,e]
        partial = [a,d], set = [b,c,e], k = 1 -> [a,d,b], [a,d,c], [a,d,e]
        partial = [a,e], set = [b,c,d], k = 1 -> [a,e,b], [a,e,c], [a,e,d]
    partial = [b], set = [a,c,d,e], k = 2
        partial = [b,a], set = [c,d,e], k = 1 -> [b,a,c], [b,a,d], [b,a,e]
        partial = [b,c], set = [a,d,e], k = 1 -> [b,c,a], [b,c,d], [b,c,e]
        partial = [b,d], set = [a,c,e], k = 1 -> [b,d,a], [b,d,c], [b,d,e]
        partial = [b,e], set = [a,c,d], k = 1 -> [b,e,a], [b,e,c], [b,e,d]
    partial = [c], set = [a,b,d,e], k = 2
        partial = [c,a], set = [b,d,e], k = 1 -> [c,a,b], [c,a,d], [c,a,e]
        partial = [c,b], set = [a,d,e], k = 1 -> [c,b,a], [c,b,d], [c,b,e]
        partial = [c,d], set = [a,b,e], k = 1 -> [c,d,a], [c,d,b], [c,d,e]
        partial = [c,e], set = [a,b,d], k = 1 -> [c,e,a], [c,e,b], [c,e,d]
    partial = [d], set = [a,b,c,e], k = 2
        partial = [d,a], set = [b,c,e], k = 1 -> [d,a,b], [d,a,c], [d,a,e]
        partial = [d,b], set = [a,c,e], k = 1 -> [d,b,a], [d,b,c], [d,b,e]
        partial = [d,c], set = [a,b,e], k = 1 -> [d,c,a], [d,c,b], [d,c,e]
        partial = [d,e], set = [a,b,c], k = 1 -> [d,e,a], [d,e,b], [d,e,c]
    partial = [e], set = [a,b,c,d], k = 2
        partial = [e,a], set = [b,c,d], k = 1 -> [e,a,b], [e,a,c], [e,a,d]
        partial = [e,b], set = [a,c,d], k = 1 -> [e,b,a], [e,b,c], [e,b,d]
        partial = [e,c], set = [a,b,d], k = 1 -> [e,c,a], [e,c,b], [e,c,d]
        partial = [e,d], set = [a,b,c], k = 1 -> [e,d,a], [e,d,b], [e,d,c]

function kSubsetPermutations(set, k, partial) {
    if (!partial) partial = [];                 // set default value on first call
    for (var element in set) {
        if (k > 1) {
            var set_copy = set.slice();         // slice() creates copy of array
            set_copy.splice(element, 1);        // splice() removes element from array
            kSubsetPermutations(set_copy, k - 1, partial.concat([set[element]]));
        }                                       // a.concat(b) appends b to copy of a
        else document.write("[" + partial.concat([set[element]]) + "] ");
    }
}
kSubsetPermutations([1,2,3,4,5], 3);

Answer 3

我是一个简单的人：

创建一个大小为 k 的数组 M

用零填充 M

循环这个：

M[0] += 1

遍历 M: *if (M[i] >= N 的大小) 然后设置 M[i]=0 并增加 M[i+1] += 1

如果 M 只有不同的数字，那么你已经找到了 a 的索引 n

的子集

当 M 的最后一个元素达到 n 减一的大小时，循环结束 a.k.a。当 * 条件会导致错误时

Answer 4

你可以使用生成器函数。

function* permutation(array, k, head = []) {
    if (!k) {
        yield head;
        return;
    };
    for (let i = 0; i < array.length; i++) {
        yield* permutation(array.filter((_, j) => j !== i), k - 1, [...head, array[i]]);
    }
}

// example 1
const p = permutation([1, 2, 3, 4, 5, 6], 4);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);

// example 2
[...permutation([1, 2, 3, 4], 3)].forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 5

这是一个不太聪明的版本，除了生成器函数（不是那么现代）之外，没有使用 JavaScript 的任何“现代”功能。与这里的大多数解决方案不同，即使输入有重复，这个解决方案也能正常工作。（它只产生每个唯一的排列一次。）

它避免了对 Sets 和 Maps 等关联数据类型的需求，因为它永远不会生成相同的排列两次。那个，再加上它避免了不必要的内部结构副本，确实使它相当快；至少，它似乎比这个问题的任何其他答案都快得多。（快速，我的意思是“每个排列”。JSBench 以每秒 430 万个 3 排列和每秒约 300 万个 6 排列，运行在 Chrome 在我的 consumer-level笔记本电脑。）

生成器是实现组合枚举最自然的方式。试图在数组中累积数百万（或更多）备选方案会导致内存耗尽；搜索的规模 space 很快就会失控。根据以上数字，尝试搜索数亿个排列是合理的。（这将需要几分钟，也许更多，具体取决于您检查每个排列的速度。不过，出于研究目的，几分钟是可以的。）但是构建一个包含数亿个排列的数组会减慢速度很多，如果它甚至可能在您使用的机器上。在绝大多数组合搜索中，不需要这样的数组。您可以在生成每个候选人时对其进行处理，或者至少过滤生成的候选人以积累（much）更小的可行候选人列表进一步处理。

如果生成器由于某种原因让您感到紧张，您可以使用一个额外的参数来指定每个候选函数要调用的函数。或者您可以使用混合方法，使用检查功能来决定是否 yield 候选人。如果您可以快速放弃大部分可能性，那可能是一个更好的架构，因为通过几个层展开 yield* 比仅仅调用一个函数要慢很多。

以下片段的部分内容来自 @NinaScholz。谢谢！

function* kperm(arr, k) {
    let data = arr.slice().sort();
    k = Math.min(k, data.length);

    function* helper(i) {
        if (i == k) 
            yield data.slice(0, k);
        else {
            for (let j = i+1; j < data.length; j++) {
                if (data[j] != data[i]) {
                    yield* helper(i+1);
                    const tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
            yield* helper(i+1);
            const tmp = data[i];
            for (let j = i+1; j < data.length; j++)
                data[j-1] = data[j];
            data[data.length - 1] = tmp;
        }
    }
    yield* helper(0);
}
// example 1
console.log("Example 1, first 8 permutations");
const p = kperm([1, 2, 3, 4, 1, 2, 3, 4], 4);
for (let i = 1; i < 8; ++i) 
    console.log(...p.next().value);

console.log("Example 2");
[...kperm([1, 2, 1, 2, 2], 4)].forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 6

我真的不明白较新的 Set 和 Map 在这里有什么帮助。但这是一个相当简单的递归版本：

const nPermutations = (xs, n) =>
  xs .length < 1 || n < 1
    ? [[]]
    : xs .flatMap (
        (x, i) => nPermutations(
          [...xs .slice (0, i), ...xs .slice (i + 1)],
          n - 1
        ). map (p => [x, ...p])
      )

console .log (nPermutations ([1, 2, 3], 2))

.as-console-wrapper {max-height: 100% !important; top: 0}

实际上，我可能会提取一个函数来创建不包括一个索引的数组副本，如下所示：

const excluding = (i, xs) =>
  [...xs .slice (0, i), ...xs .slice (i + 1)]

const nPermutations = (xs, n) =>
  xs .length < 1 || n < 1
    ? [[]]
    : xs .flatMap (
        (x, i) => nPermutations (excluding (i, xs), n - 1). map (p => [x, ...p])
      )

给定一个数组，如何生成子集大小为 k 的所有组合？

Given an array, how to generate all combinations of subset size k?

javascript

algorithm

permutation

subset

combinatorics