查找指定大小的所有子集

Question

我已经为这个问题绞尽脑汁两天了，但我无法想出解决方案。我正在寻找的是一个函数

f(s, n)

，它返回一个包含

s

的所有子集的集合，其中每个子集的长度为

n

。

演示：

s={a, b, c, d}

f(s, 4)
{{a, b, c, d}}

f(s, 3) 
{{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}}

f(s, 2)
{{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}

f(s, 1)
{{a}, {b}, {c}, {d}}

我有一种感觉，递归是解决这个问题的方法。我一直在摆弄类似的东西

f(S, n):
   for s in S:
       t = f( S-{s}, n-1 ) 
       ...

但这似乎并不能解决问题。我确实注意到

len(f(s,n))

似乎是二项式系数

bin(len(s), n)

。我想这可以以某种方式利用。

你能帮我吗？

Answer 1

让我们将数组的大小称为

n

，并将子数组中要包含的元素数量称为

k

。

让我们考虑数组

A[0]

的第一个元素

A

。
如果这个元素放入子集中，问题就变成了

(n-1, k-1)

类似的问题。
如果没有，那就变成了

(n-1, k)

问题。

这可以简单地用递归函数实现。

我们只要注意处理极端情况

k == 0

或

k > n

。

在这个过程中，我们还要记录：

• n：A 中要考虑的剩余元素的数量

• k：当前子集中剩余要放入的元素数量

• index：A 中要考虑的下一个元素的索引

• current_subset

  数组，用于存储已选择的元素。

  这是一个简单的c++代码来说明算法

输出

对于 5 个元素和大小为 3 的子集：

3 4 5
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3

#include    <iostream>
#include    <vector>

void print (const std::vector<std::vector<int>>& subsets) {
    for (auto &v: subsets) {
        for (auto &x: v) {
            std::cout << x << " ";
        }
        std::cout << "\n";
    }
}
//  n: number of remaining elements of A to consider
//  k: number of elements that remain to be put in the current subset
//  index: index of next element of A to consider

void Get_subset_rec (std::vector<std::vector<int>>& subsets, int n, int k, int index, std::vector<int>& A, std::vector<int>& current_subset) {
    if (n < k) return;   
    if (k == 0) {
        subsets.push_back (current_subset);
        return;
    }  
    Get_subset_rec (subsets, n-1, k, index+1, A, current_subset);
    current_subset.push_back(A[index]);
    Get_subset_rec (subsets, n-1, k-1, index+1, A, current_subset);
    current_subset.pop_back();         // remove last element
    return;
}

void Get_subset (std::vector<std::vector<int>>& subsets, int subset_length, std::vector<int>& A) {
    std::vector<int> current_subset;
    Get_subset_rec (subsets, A.size(), subset_length, 0, A, current_subset);
}

int main () {
    int subset_length = 3;     // subset size
    std::vector A = {1, 2, 3, 4, 5};
    int size = A.size();
    std::vector<std::vector<int>> subsets;

    Get_subset (subsets, subset_length, A);
    std::cout << subsets.size() << "\n";
    print (subsets);
}

现场演示

Answer 2

解决这个问题的一种方法是回溯。这是伪代码中可能的算法：

def backtrack(input_set, idx, partial_res, res, n):
  if len(partial_res == n):
    res.append(partial_res[:])
    return
  
  for i in range(idx, len(input_set)):
    partial_res.append(input_set[i])
    backtrack(input_set, idx+1, partial_res, res, n) # path with input_set[i]
    partial_res.pop()
    backtrack(input_set, idx+1, partial_res, res, n) # path without input_set[i]

这种方法的时间复杂度为

O(2^len(input_set))

，因为我们在

input_set

的每个元素处创建 2 个分支，无论路径是否导致有效结果。空间复杂度为

O(len(input_set) choose n)

，因为这是您获得的有效子集的数量，正如您在问题中正确指出的那样。

现在，有一种方法可以优化上述算法，通过将递归树修剪为仅能得出有效结果的路径，将时间复杂度降低到

O(len(input_set) choose n)

。

如果

n - len(partial_res) < len(input_set) - idx + 1

，我们确信即使我们取出了

input_set[idx:]

中的所有剩余元素，我们仍然至少缺少一个来达到

n

。所以我们可以用它作为基本情况并返回和修剪。

此外，如果

n - len(partial_res) == len(input_set) - idx + 1

，这意味着我们需要

input_set[idx:]

中的每个元素来获得所需的

n

长度结果。因此，我们无法跳过任何元素，因此递归调用的第二个分支变得多余。

backtrack(input_set, idx+1, partial_res, res, n) # path without input_set[i]

我们可以通过条件检查跳过这个分支。 正确实现这些基本情况，可以将算法的时间复杂度降低到

O(len(input_set) choose k)

，这是一个硬限制，因为这是子集的数量。

Answer 3

subseqs 0 _      = [[]]
subseqs k []     = []
subseqs k (x:xs) = map (x:) (subseqs (k-1) xs) ++ subseqs k xs

现场演示

该函数在给定序列中查找（非负）长度 k 的子序列。分三种情况：

1. 如果长度为0：任意序列中都存在一个空子序列。
2. 否则，如果序列为空：则不存在任何（正）长度 k 的子序列。
3. 否则，存在一个以

   x

   开头并以

   xs

   继续的非空序列，且长度为正数

   k

   。我们所有的子序列都有两种：包含

   x

   的子序列（它们是长度为

   xs

   的

   k-1

   的子序列，每个序列的前面都有

   x

   ），以及不包含

   x

   的子序列（它们只是长度为

   xs

   的

   k

   的子序列）。

该算法或多或少是这些注释对 Haskell 的直译。符号备忘单：

• []

  空列表

• [w]

  包含单个元素的列表

  w

• x:xs

  一个列表，头部为

  x

  ，尾部为

  xs

• (x:)

  一个将

  x

  粘贴在任何列表前面的函数

• ++

  列表串联

• f a b c

  函数

  f

  应用于参数

  a

  b

  和

  c

Answer 4

这是一个非递归 python 函数，它接受一个列表

superset

并返回一个生成器，该生成器生成大小为

k

的所有子集。

def subsets_k(superset, k):
  if k > len(superset):
    return
  if k == 0:
    yield []
    return

  indices = list(range(k))
  while True:
    yield [superset[i] for i in indices]

    i = k - 1
    while indices[i] == len(superset) - k + i:
      i -= 1
      if i == -1:
        return
    
    indices[i] += 1
    for j in range(i + 1, k):
      indices[j] = indices[i] + j - i

测试：

for s in subsets_k(['a', 'b', 'c', 'd', 'e'], 3):
  print(s)

输出：

['a', 'b', 'c']
['a', 'b', 'd']
['a', 'b', 'e']
['a', 'c', 'd']
['a', 'c', 'e']
['a', 'd', 'e']
['b', 'c', 'd']
['b', 'c', 'e']
['b', 'd', 'e']
['c', 'd', 'e']

Answer 5

问题陈述：
对于给定的一维数字数组，找到所有可能的子集 具有特定长度的数组，例如 对于数组 [1,2,3] 如果我们想找到长度为 2 的所有子集那么 输出应该是

[
  [1,2],
  [1,3],
  [2,3]
]

解决方案：

function getAllSubsetsOfSpecificLength(array, length) {
  const subsets = [[]];
  const subsetsOfSpecificLength = [];

  for (const el of array) {
    const last = subsets.length - 1;
    for (let i = 0; i <= last; i++) {
      let set = [...subsets[i], el];
      subsets.push(set);

      if (set.length == length) {
        subsetsOfSpecificLength.push(set);
      }

      if (set.length > length) {
        break;
      }
    }
  }

  return subsetsOfSpecificLength;
}
let array = [1, 2, 3];
let result = getAllSubsetsOfSpecificLength(array, 2);
console.log(result);

输出：

[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]