（C++）设计算法求集合｛1,2,...,n｝的幂集

╰+哭是因爲堅強的太久メ 2023-02-26 08:24 160阅读 0赞

集合A的幂集是由集合A的所有子集所组成的的集合。

如：A=\{1，2，3\}，则A的幂集P（A）=\{ \{1，2，3\}，\{1，2\}，\{1，3\}，\{1\}，\{2，3\}，\{2\}，\{3\}，\{ \}\}。

求一个集合的幂集就是求一个集合的所有的子集，方法有穷举法，分治法，回溯等

输入：n

输出：集合｛1,2,...,n｝的幂集

--------------------

这里采用一个递归的解法，递归思想如下：

0 -> \{\}

1 -> \{\} \{1\}

2 -> \{\} \{1\}\{ **2**\} \{1,**2**\}    说明：就是1得出的结果每个都加上2，和原来的1的幂集构成新的幂集。

3 -> \{\} \{1\} \{2\} \{1,2\}\{ **3**\} \{1,**3**\} \{2,**3**\} \{1,2,**3**\}  说明：前半部分和2还是一摸一样，后半部分就是2的结果每个都添个3。

…… 不过这个想法我似乎没实现

--------------------

第二个想法：\{1，2，3\}的幂集就是选择每个集合内元素是否出现，即1出现与否，2出现与否，3出现与否... 然后想要得到所有结果就遍历0-7，即000-111。0或者1代表了该元素是否被选取。于是有了代码里的 移位(<<) 与(&) 操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

--------------------

#include <iostream> 
    #include <math.h> 
    using namespace std; 
    
    void printPowerSet(int *set, int set_size) 
    { 
    	unsigned int pow_set_size = pow(2, set_size);    // 幂集集合个数为2^n 
    	int counter, j; 
    	
    	/*Run from counter 000..0 to 111..1*/
    	for(counter = 0; counter < pow_set_size; counter++) { 
    		cout<<"{";
    		for(j = 0; j < set_size; j++) { 
    			/* 1<<0 = 1	 1<<1 = 10	1<<2 = 100
    			eg.counter = 7 = 111    
    			那么  set[0] set[1] set[2]都要输出 
    			*/
    			if(counter & (1 << j)) 
    				cout << set[j]<<" "; 
    		} 
    		cout<<"}"; 
    	} 
    } 
    
    
    /*Driver code*/
    int main() 
    { 
    	cout<<"n=?"<<endl;
    	int n;
    	cin>>n; 
    	int set[n];
    	for (int i=0;i<n;i++) set[i] = i+1;
    	printPowerSet(set, n); 
    	return 0; 
    }

> n=?  
> 3  
> \{\}\{1 \}\{2 \}\{1 2 \}\{3 \}\{1 3 \}\{2 3 \}\{1 2 3 \}  
> \--------------------------------

实现的磕磕巴巴的，好难，还是参考别人的，我真菜，真的。

--------------------

参考：

[https://www.geeksforgeeks.org/power-set/][https_www.geeksforgeeks.org_power-set]

[https://www.bilibili.com/video/BV1PE411f7Kx?t=294][https_www.bilibili.com_video_BV1PE411f7Kx_t_294]

[https://stackoverflow.com/questions/41629583/if-counter-1j-what-does-this-statement-mean-and-how-it-works/41629671\#41629671][https_stackoverflow.com_questions_41629583_if-counter-1j-what-does-this-statement-mean-and-how-it-works_41629671_41629671]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/5f4635074187447dbd920c40bb8fdbfb.png
[https_www.geeksforgeeks.org_power-set]: https://www.geeksforgeeks.org/power-set/
[https_www.bilibili.com_video_BV1PE411f7Kx_t_294]: https://www.bilibili.com/video/BV1PE411f7Kx?t=294
[https_stackoverflow.com_questions_41629583_if-counter-1j-what-does-this-statement-mean-and-how-it-works_41629671_41629671]: https://stackoverflow.com/questions/41629583/if-counter-1j-what-does-this-statement-mean-and-how-it-works/41629671#41629671