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

Question

假设有input = [1, 2, 3]和k=2，那么返回结果如下：

1 2
1 3
2 1
2 3
3 1
3 2

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

注：该链接提供了从给定数组中打印子集大小为k的所有组合的算法。

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等结果。

其次，我不确定我是否正确地命名了这个问题，因为“大小为k的所有子集的所有组合”的解决方案并未给出预期答案。

- atkayla

---

{btsdaf} - Anil

@AncientSwordRage 你是在寻找迭代解决方案吗？ - the Hutt

@Onkar不在这里，只是一个更高效的更新。 - AncientSwordRage

Answer 1

一个递归解决方案用于查找k子集排列（伪代码）：
```
function kSubsetPerms(set, k):
if k == 0:
yield []
else:
for i in range(len(set)):
for perm in kSubsetPerms(set[i+1:], k-1):
yield [set[i]] + perm
```

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)
        }
    }
}

以下是一个示例：

输入：[a,b,c,d,e]
k: 3

（注：本文涉及 IT 技术）

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);

- m69 ''snarky and unwelcoming''

---

{btsdaf} - m69 ''snarky and unwelcoming''

{btsdaf} - atkayla

{btsdaf} - m69 ''snarky and unwelcoming''

如何编辑此代码以返回数组的数组，而不是编写字符串？ - Gabe Conant

Answer 2

你可以使用生成器函数。

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; }

- Nina Scholz

Answer 3

这里提供的版本不会过于聪明，也不使用除生成器函数（不算太现代）之外的任何“现代”JavaScript特性。与这里大多数解决方案不同的是，即使输入有重复，此方法也能正常工作（只会产生每个唯一排列一次）。通过从不再次生成相同的排列，它避免了对集合和映射等关联数据类型的需求。这样加上它避免了内部结构不必要的副本，使其变得相当快；至少它似乎比这个问题的任何其他答案都要快。 （快的意思是“每个排列”。在我的消费级笔记本电脑上运行Chrome，JSBench的速率为430万个3个元素排列/秒，以及约300万个6个元素排列/秒。）

生成器是实现组合枚举的最自然方式。试图在数组中积累数百万个备选项或更多，会导致内存耗尽；搜索空间的大小很快就会失控。根据上面的数字，尝试遍历数亿个排列是合理的。（这将需要几分钟，也许更长时间，具体取决于您可以多快地检查每个排列。但是，几分钟对于研究目的来说还是可以接受的。）但是，构造数亿个排列的数组会大大减慢事情的速度，如果在您使用的机器上甚至有可能实现的话。在绝大多数组合搜索中，没有必要使用这样的数组。您可以处理生成的每个候选项，或者至少过滤生成的候选项以累积一个（更小的）可行候选列表以供进一步处理。

如果生成器令您感到不安，您可以使用一个附加参数来指定一个函数，用于处理每个候选项。或者您可以使用混合架构，使用检查函数来决定是否 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; }

- rici

---

我认为我理解了这个过程，但我不确定...它是在主数组中进行洗牌以获得每个排列的不同顺序吗？ - AncientSwordRage

@AncientSwordRage：是的，那就是算法的基础。但它会在自己的数组副本上运行 (let data = arr.slice().sort();)。它必须对数组进行排序，以防数组包含重复项。（实际上，它只需要将相等的值分组在一起；排序是过度处理了。但是JS没有一个仅仅分组的函数。） - rici

请注意，递归深度受k限制，而不是数组长度。因此，您不会使堆栈溢出。算法非常直观。该数组在逻辑上分为正在构建的排列的前缀和其余元素的储备池。对于储备池中的每个（唯一）元素，它将其添加到前缀中并递归调用以完成。由于它是回溯算法，因此需要确保返回时数组与进入时的顺序相同。它实现这一点的方式实际上是唯一略有巧妙的部分。 - rici

使用输入数组作为部分前缀和蓄水池的技巧对于重复较少的数组非常有效，但是如果有大量重复，最好使用类似于多集合的东西作为蓄水池。我也有一个实现；对于实际使用的数组来说，它可能快两倍。（尽管您的用例不太实际 :-(. ） - rici

@onkar：为什么它要产生12个结果？只有七种可能的排列方式：两个不同值的六种可能性，以及[1,1]。基准测试在https://jsbench.me/3kkyricqfe。 - rici

Answer 4

我不是很清楚新的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])
      )

- Scott Sauyet

Answer 5

不要使用组合，尝试使用排列。

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

这里是实现方法，修改自此处

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)));

- phlaxyr

---

{btsdaf} - phlaxyr

{btsdaf} - atkayla

Answer 6

我是一个简单的人：

创建大小为k的数组M

用零填充M

循环执行以下操作：

M[0] += 1

遍历M：*如果(M[i] ≥ N的大小)，则将M[i]设置为0，并增加M[i+1] += 1

如果M仅包含不同的数字，则找到了n的子集的索引

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

- Steve