给定一个大小为n的数组，输出所有全排列。
1、数组中无重复元素：从前到后，依次将数组中的元素放置在输出数组中，若放完就输出，然后递归的改变元素的位置，直到输出所有的全排列。递归中使用一个标记数组来记录某个元素是否已经被放置过。
2、数组中有重复元素：这个和1比较类似，区别在于用一个标记数组记录某个元素的次数，每放置一次就减一。
问题1的代码如下：
void PermRecur(vector<int>& ivec, vector<int>& use, vector<int>& res, int k)
{
//如果下标k等于size，说明所有元素已经放置完毕
if (k == ivec.size())
{
for (int i = 0; i < k; ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = 0; i < ivec.size(); ++i)
{
//标记为0表示没有被放置过
if (use[i] == 0)
{
//元素被放置后将标记赋为1
use[i] = 1;
res[k] = ivec[i];
PermRecur(ivec, use, res, k + 1);
//递归结束后再将该元素的标记赋为0
use[i] = 0;
}
}
}
void Perm(vector<int>& ivec)
{
int size = ivec.size();
assert(size > 0);
//所有元素的标记为初始化为0
vector<int> use(size);
vector<int> res(size);
PermRecur(ivec, use, res, 0);
}
void main()
{
int a[] = {1, 2, 3};
vector<int> ivec(a, a + 3);
Perm(ivec);
}
问题2的代码如下：
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
void PermRecur(vector<int>& num, vector<int>& use, vector<int>& res, int k)
{
//如果下标k等于size，说明所有元素已经放置完毕
if (k == res.size())
{
for (int i = 0; i < k; ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = 0; i < num.size(); ++i)
{
//标记大于0说明还有剩余的元素没有放置
if (use[i] > 0)
{
//元素被放置后次数减1
--use[i];
res[k] = num[i];
PermRecur(num, use, res, k + 1);
//递归结束后再将该元素的次数加1
++use[i];
}
}
}
void Perm(vector<int>& ivec)
{
assert(!ivec.empty());
int size = ivec.size();
vector<int> res(size);
vector<int> use;
vector<int> num;
//根据ivec统计每个元素的出现次数，并将去重后的所有元素存在num中
use.push_back(1);
num.push_back(ivec[0]);
for (int i = 1; i < size; ++i)
{
int j = 0;
for (; j < i; ++j)
{
if (ivec[i] == ivec[j])
{
++use[j];
break;
}
}
if (j == i)
{
use.push_back(1);
num.push_back(ivec[i]);
}
}
PermRecur(num, use, res, 0);
}
void main()
{
int a[] = {1, 2, 2};
vector<int> ivec(a, a + 3);
Perm(ivec);
}
给定一个大小为n的数组，输出所有的子集。子问题是从n个元素中选择m个元素，然后循环调用即可。
1、数组中无重复的元素：从前到后依次将数组中的元素放置到输出数组中，当元素个数达到m时输出即可。然后进行递归，将剩余的元素和m个元素进行交换。
2、数组中有重复的元素：和全排列类似，先去重并计算元素的次数，然后进行递归。
问题1的代码如下：
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
void CombRecur(vector<int>& ivec, vector<int>& res, int m, int begin, int k)
{
//当k等于m的时候输出结果
if (k == m)
{
for (int i = 0; i < res.size(); ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = begin; i < ivec.size(); ++i)
{
res[k] = ivec[i];
CombRecur(ivec, res, m, i + 1, k + 1);
}
}
void Comb(vector<int>& ivec)
{
assert(!ivec.empty());
for (int i = 1; i <= ivec.size(); ++i)
{
vector<int> res(i);
CombRecur(ivec, res, i, 0, 0);
}
}
void main()
{
int a[] = {1, 2, 3};
vector<int> ivec(a, a + 3);
Comb(ivec);
}
问题2的代码如下：
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
void CombRecur(vector<int>& num, vector<int>& use, vector<int>& res,
int m, int begin, int k)
{
//当k等于m时，说明已经选够m个元素
if (k == m)
{
for (int i = 0; i < res.size(); ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = begin; i < num.size(); ++i)
{
//如果元素次数大于0就选择
if (use[i] > 0)
{
//选择之后就将元素次数减1
--use[i];
res[k] = num[i];
//这里递归的时候begin仍然是i，因为第i个元素有可能重复
CombRecur(num, use, res, m, i, k + 1);
++use[i];
}
}
}
void Comb(vector<int>& ivec)
{
assert(!ivec.empty());
int size = ivec.size();
vector<int> num;
vector<int> use;
//根据ivec统计每个元素的出现次数，并将去重后的所有元素存在num中
num.push_back(ivec[0]);
use.push_back(1);
for (int i = 1; i < size; ++i)
{
int j = 0;
for (; j < i; ++j)
{
if (ivec[i] == ivec[j])
{
++use[j];
break;
}
}
if (j == i)
{
use.push_back(1);
num.push_back(ivec[i]);
}
}
//从1~n循环调用即可求出大小为1~n的所有子集
for (int i = 1; i <= size; ++i)
{
vector<int> res(i);
CombRecur(num, use, res, i, 0, 0);
}
}
void main()
{
int a[] = {1, 2, 2};
vector<int> ivec(a, a + 3);
Comb(ivec);
}