说明
我目前初学算法,所以语言上应该会比算法大佬们通俗很多。考虑到方便性,我使用的伪代码为基于 php 加上一些自然语言处理的代码,可以比直接写 C++ 代码更容易理解。文章末尾会附上我的 C++ 代码。
原理分析
首先看原理。
现有集合 set = [1, 2, 3]
。设有一个空集 setToAppend = []
。
挑出 set[0] = 1
。
向 setToAppend
添加 1
或不添加 1
,可得到两个集合 [1]
与 []
。
[]
+-- []
+-- [1]
挑出 set[1] = 2
。
向刚才生成的两个集合中的 [1]
添加 2
或不添加 2
,可得到两个集合 [1, 2]
与 [1]
。
向刚才生成的两个集合中的 []
添加 2
或不添加 2
,可得到两个集合 [2]
与 []
。
[]
+-- []
+--[2]
+--[]
+-- [1]
+--[1, 2]
+--[1]
对于产生的四个集合,再分别添加 3
或不添加 2
,可得到八个集合:
[]
+-- []
+-- [2]
+-- [2, 3]
+-- [2]
+-- []
+-- [3]
+-- []
+-- [1]
+-- [1, 2]
+-- [1, 2, 3]
+-- [1, 2]
+-- [1]
+-- [1, 3]
+-- [1]
这八个集合就是 [1, 2, 3]
的所有子集了:
[2, 3],
[2],
[3],
[],
[1, 2, 3],
[1, 2],
[1, 3],
[1]
这就是子集生成的原理。那么如何转写为代码呢?
参数分析与伪代码表述
首先看涉及到哪些变量。
- 集合
set = [1, 2, 3]
。 - 当前的下标
index
。 - 被追加的集合
setToAppend
(也就是一开始的空集) - 生成的集合
setGenerated
(也就是之后被追加的集合)
所以我们设计一个函数 subset:
function subset($set, $index = 0, $setToAppend = [], $setGenerated = []){
}
然后怎么做?回顾我们的自然语言表述:
挑出
set[0] = 1
。向
setToAppend
添加1
或不添加1
,可得到两个集合[1]
与[]
。
翻译成伪代码:
function subset($set, $index = 0, $setToAppend = [], $setGenerated = null){
$numberToAdd = $set[$index]; // 要用于添加的数字
$generatedSet1 = $setToAppend; // 产生的第一个集合
$generatedSet2 = $setToAppend.append($numberToAdd); // 产生的第二个集合
}
由于我们把生成的两个集合分别对待,所以参数中的 $setGenerated 相当于分开写了。可以删掉。
function subset($set, $index = 0, $setToAppend = []){
// ...
}
接下来,要针对生成的两个集合,再执行一次生成操作:
function subset($set, $index = 0, $setToAppend = []){
// ...(之前的代码)
$index++; // 由于生成用的数字是下一位,所以索引自增了。
$setToAppend1 = $generatedSet1;
$setToAppend2 = $generatedSet2;
// 由于生成了两个集合,所以两个都要分别继续生成
subset($set, $index, $setToAppend1);
subset($set, $index, $setToAppend2);
}
现在差不多了,还缺少的就是终止条件。我们可以注意到,如果 $index
自增之后,超出了 $set 的范围,也即 $set.size == $index
时,就应该中止了。根据之前的分析,最后生成的集合就是真正的子集了:
function subset($set, $index = 0, $setToAppend = []){
if($set.size == $index){
print($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
return;
}
// ...(之前的代码)
}
考虑到要将结果存放起来,我们可以增加一个引用传值的参数,用来存放结果。
function subset(&$result, $set, $index = 0, $setToAppend = []){
if($set.size == $index){
$result.append($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
return;
}
// ...
}
现在程序的全貌是这样的:
function subset(&$result, $set, $index = 0, $setToAppend = []){
if($set.size == $index){
$result.append($setToAppend) // setToAppend 也就是之前生成的集合 generatedSet。
return;
}
$numberToAdd = $set[$index]; // 要用于添加的数字
$generatedSet1 = $setToAppend; // 产生的第一个集合
$generatedSet2 = $setToAppend.append($numberToAdd); // 产生的第二个集合
$index++; // 由于生成用的数字是下一位,所以索引自增了。
$setToAppend1 = $generatedSet1;
$setToAppend2 = $generatedSet2;
// 由于生成了两个集合,所以两个都要分别继续生成
subset($result, $set, $index, $setToAppend1);
subset($result, $set, $index, $setToAppend2);
}
现在,转写为编程语言吧。
编程语言表述
/**
* 输出一个集合的所有子集
*/
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void subsets(vector<vector<T>> &result, const vector<T> &originSet, size_t index, vector<T> setToAppend)
{
if (originSet.size() == index)
{
if (setToAppend.size() >= 0)
{
result.push_back(setToAppend);
}
return;
}
vector<T> setToAppend1 = setToAppend;
setToAppend.push_back(originSet[index]);
vector<T> setToAppend2 = setToAppend;
index++;
subsets(result, originSet, index, setToAppend1);
subsets(result, originSet, index, setToAppend2);
}
template <class T>
void printSet(vector<vector<T>> set)
{
cout << "set: " << endl;
for (size_t i = 0; i < set.size(); i++)
{
vector<T> subset = set[i];
cout << "{";
for (size_t j = 0; j < subset.size(); j++)
{
cout << subset[j];
if (j != subset.size() - 1)
{
cout << ", ";
}
}
cout << "}" << endl;
}
}
int main()
{
vector<vector<int>> result;
subsets(result, {1, 2, 3, 4, 5, 6, 7, 8, 9}, 0, {});
printSet<int>(result);
return 0;
}