8、若S是n个元素的集合，则S的幂集P(S)定义为S的所有子集的集合。例如，S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}。给定S，写一递归算法求P(S)。（本题20分）
#include <iostream>
#include <deque>
// 《数据结构》严蔚敏P150 例6.3
void PrintPowerSet(int i, int n)
{
static std::deque<int> set;
if (i > n)
{
for (unsigned j = 0; j < set.size(); j++)
{
std::cout << set[j] << " ";
}
std::cout << std::endl;
}
else
{
set.push_back(i);
PrintPowerSet(i + 1, n);
set.erase(std::find(set.begin(), set.end(), i));
PrintPowerSet(i + 1, n);
}
}
template <typename T>
void PrintPowerSet(const T * a, int left, int right)
{
static std::deque<T> set;
if (left > right)
{
for (unsigned i = 0; i < set.size(); i++)
{
std::cout << a[set[i]] << " ";
}
std::cout << std::endl;
}
else
{
set.push_back(left);
PrintPowerSet(a, left + 1, right);
set.erase(std::find(set.begin(), set.end(), left));
PrintPowerSet(a, left + 1, right);
}
}
int main()
{
// 1.[-2, 3]区间内整数的全组合输出
PrintPowerSet(-2, 3);
// 2.用于下标即可实现数组元素全组合打印
char a[6] = {'A', 'B', 'C', 'D', 'E', 'F'};
PrintPowerSet(a, 0, 5);
return 0;
}
9. 对输入的任意正整数n，打印出集合{0, 1, 2, ..., n - 1}的所有非空子集
#include <iostream>
int main()
{
unsigned n = 5;// {0， 1， 2， 3， 4}的全部非空子集
unsigned m = 1;
for (unsigned i = 0; i < n; i++)
m *= 2;
m--;
printf("m = %d\n", m);// 非空子集数
for (unsigned i = 1; i <= m; i++)
{
unsigned j = i;
unsigned k = 0;
while (j > 0)
{
if (j % 2)
printf("%d ", k);
k++;
j /= 2;
}
printf("\n");
}
return 0;
}
方便：将问题转化为利用algorithm中的排列方法对01数组排列，目测优点是可以对付数量很大的情况
#include <stdio.h>
#include <algorithm>
// 显示在长度为n的数组a[]中取m个元素的全部取法
template <typename T>
void dispPowerSet(const T a[], unsigned n, unsigned m)
{
bool * mark = (bool *)malloc(sizeof(bool) * n);// 将问题转化为对{1, 1, 1, 0, 0}数组的全排列，如果为1，则a[]中相应下标元素被选中
for (size_t i = 0; i < m; i++)
{
mark[i] = true;
}
for (size_t i = m; i < n; i++)
{
mark[i] = false;
}
do
{
// 对每种取法的操作
for (size_t i = 0; i < n; i++)
{
if (mark[i])
{
printf("%d ", a[i]);
}
}
printf("\n");
} while (std::prev_permutation(mark, mark + n));
free(mark);
}
int main()
{
int a[] = {1, 2, 3, 4, 5};
dispPowerSet(a, 5, 3);
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-950019.html
