集合的幂集

/*
 *
 * */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int INF = ~0u>>1;
typedef pair  P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<= len){
        if (b[0]) cout << b << endl;
        else cout << "空集" << endl;
    }
    else {
        x = s[i];
        k = strlen(b);
        b[k] = x;
        GetPowerSet(i+1,s);
        b[k] = 0;
        GetPowerSet(i+1,s);
    }
}

int main(){
    while (~scanf("%s",a)){
        printf("%s的幂集是:n", a);
        print();
        GetPowerSet(0,a);
        print();
    }
    return 0;
}

实现之后
sdfea
sdfea的幂集是:
--------
sdfea
sdfe
sdfa
sdf
sdea
sde
sda
sd
sfea
sfe
sfa
sf
sea
se
sa
s
dfea
dfe
dfa
df
dea
de
da
d
fea
fe
fa
f
ea
e
a
空集
--------

**<span style="background-color: transparent; border: 0px; margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(255, 102, 0); background-position: initial initial; background-repeat: initial initial;">集合A的幂集是由集合A的所有子集所组成的的集合。</span>**

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">若![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)是集合![{a, b, c}](http://upload.wikimedia.org/math/3/2/9/3294dff896d06fea4749ce99aa43eb28.png)，则![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的全部子集如下：</span></span>

• （空集）</span>
• </span>
• </span>
• </span>
• </span>
• </span>
• </span>

• </span>

  因此的幂集为</span>

, , , , , , , 。

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">幂集中的每个元素是一个集合，它或是空集，或含集合A中一个元素，或含集合A中两个元素&hellip;&hellip; 或等于集合A。反之，从集合A 的每个元素来看，它只有两种状态：它或属幂集的无素集，或不属幂集的元素集。则求幂集p(A)的元素的过程可看成是依次对集合A中元素进行"取舍"的过程，并且可以用一棵二叉树来表示过程中幂集元素的状态变化过程，树中的根结点表示幂集元素的初始状态（空集）；叶子结点表示它的终结状态，而第i层的分支结点，则表示已对集合A中前i-1个元素进行了取舍处理的当前状态（左分支表示取，右分支表示舍 ）。因此求幂集元素的过程即为先序遍历这棵状态树的过程。</span></span>



<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">若![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)是有限集，有![|S|=n](http://upload.wikimedia.org/math/1/1/1/1114c80010a66a42faea3d20cfa4cbd2.png)个元素，那么![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集有![|mathcal{P}(S)| = 2^n](http://upload.wikimedia.org/math/b/6/6/b66b17bd63291fa202629e3da28af7be.png)个元素。（其实可以&mdash;&mdash;电脑也如此做&mdash;&mdash;将![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的元素表示为_n_位二进制数；第_n_位表示包含或不含![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的第_n_个元素。这样的数总共有![2^n](http://upload.wikimedia.org/math/9/a/a/9aa0ec0374c89d2f7f3d9cd2e05a4bc5.png)个。）</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">我们也可以考虑无穷集的幂集。以[康托尔对角线方法](http://zh.wikipedia.org/wiki/%E5%BA%B7%E6%89%98%E7%88%BE%E5%B0%8D%E8%A7%92%E7%B7%9A%E6%96%B9%E6%B3%95 "康托尔对角线方法")可证明集合（不论是否无穷）的幂集的[基数](http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B8 "基数")总是大于原来集合的基数（粗略的说，集合的幂集大于集合本身）。例如[自然数](http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B8 "自然数")集的幂集可以[一一对应](http://zh.wikipedia.org/wiki/%E5%8F%8C%E5%B0%84 "双射")于[实数](http://zh.wikipedia.org/wiki/%E5%AF%A6%E6%95%B8 "实数")集（把一个无穷0-1序列等同于有1出现的指数的集）。</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">集合![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集，加上并、交和补运算，就得出[布尔代数](http://zh.wikipedia.org/wiki/%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0 "布尔代数")的原始例子。我们可以证明所有有限布尔代数都是同构于某有限集的幂集的布尔代数。这结果虽然对无穷布尔代数不成立，但是所有无穷布尔代数都是某个幂集布尔代数的子代数。</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">集合![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集与对称差运算构成一个[阿贝尔群](http://zh.wikipedia.org/wiki/%E9%98%BF%E8%B2%9D%E7%88%BE%E7%BE%A4 "阿贝尔群")（其中空集为幺元，每个集合的逆元为其本身），而与交运算则构成[交换](http://zh.wikipedia.org/wiki/%E4%BA%A4%E6%8F%9B%E5%BE%8B "交换律")[半群](http://zh.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4 "半群")。因此（可证明这两运算适合分配律）这两个运算使幂集成为一个[环](http://zh.wikipedia.org/wiki/%E7%92%B0 "环")。</span></span>



<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">部分来源：</span></span>[http://www.wutianqi.com/?p=1157](http://www.wutianqi.com/?p=1157)



实现代码