我已经对这个问题思考了两天，但是还是没有想出一个解决方案。我需要一个函数f(s,n)，它返回包含所有长度为n的s子集的集合。
演示：
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)。我想这可能可以在某种程度上利用。
请问我能为您提供帮助吗？
解决这个问题的一种方法是通过回溯。以下是伪代码中可能的算法：
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]
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);
}
subseqs 0 _ = [[]]
subseqs k [] = []
subseqs k (x:xs) = map (x:) (subseqs (k-1) xs) ++ subseqs k xs
该函数在给定序列中寻找长度为k的子序列。有三种情况：
x开始并继续使用xs的非空序列和一个正整数长度k。我们的所有子序列有两种类型：包含x的那些（它们是长度为k-1的xs的子序列，每个子序列的前面都有x），以及不包含x的那些（它们只是长度为k的xs的子序列）。该算法是将这些笔记逐字翻译成Haskell的结果。符号速查表：
[] 空列表[w] 一个带有单个元素w的列表x:xs 一个头部为x，尾部为xs的列表(x:) 一个将x添加到任何列表前面的函数++ 列表连接f a b c 应用于参数a，b和c的函数fsuperset并返回一个生成器，该生成器产生所有大小为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']
n的组合，因为他们的结果是无序元组@Lundin - user1984std::set带有强制排序顺序，并且您必须提前定义一种比较集合项的方法才能使用容器类。 - Lundin