C++經典演算法題-產生可能的集合
- 2020 年 2 月 13 日
- 筆記
29.Algorithm Gossip: 產生可能的集合
說明
給定一組數字或符號，產生所有可能的集合（包括空集合）， 例如給定1 2 3，則可能的集合為：
{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
解法
如果不考慮字典順序，則有個簡單的方法可以產生所有的集合，思考二進位數字加法，並注意1出現的位置，如果每個位置都對應一個數字，則由1所對應的數字所產生的就是一個集合，例如：
了解這個方法之後，剩下的就是如何產生二進位數？有許多方法可以使用，您可以使用unsigned 型別加上&位元運算來產生，這邊則是使用陣列搜 尋，首先陣列內容全為0，找第一個1，在還沒找到之前將走訪過的內容變為0，而第一個找到的0則變為 1，如此重複直到所有的陣列元素都變為1為止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111
如果要產生字典順序，例如若有4個元素，則：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} => {1,2,4} => {1,3} => {1,3,4} => {1,4} => {2} => {2,3} => {2,3,4} => {2,4} => {3} => {3,4} => {4}
簡單的說，如果有n個元素要產生可能的集合，當依序產生集合時，如果最後一個元素是n，而倒數第二個元素是m的話，例如：
{a b c d e n}
則下一個集合就是{a b c d e+1}，再依序加入後續的元素。
例如有四個元素，而當產生{1 2 3 4}集合時，則下一個集合就是{1 2 3+1}，也就是{1 2 4}，由於最後一個元素還是4，所以下一個集合就是{1 2+1}，也就是{1 3}，接下來再加入後續元素4，也就是{1 3 4}，由於又遇到元素4，所以下一個集合是{1 3+1}，也就是{1 4}。
程式碼示例
C無字典順序
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 int main(void) { char digit[MAXSIZE]; int i, j; int n; printf("輸入集合個數："); scanf("%d", &n); for(i = 0; i < n; i++) digit[i] = '0'; printf("n{}"); // 空集合 while(1) { // 找第一個0，並將找到前所經過的元素變為0 for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++); if(i == n) // 找不到0 break; else // 將第一個找到的0變為1 digit[i] = '1'; // 找第一個1，並記錄對應位置 for(i = 0; i < n && digit[i] == '0'; i++); printf("n{%d", i+1); for(j = i + 1; j < n; j++) if(digit[j] == '1') printf(",%d", j + 1); printf("}"); } printf("n"); return 0; }
C字典順序
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 int main(void) { int set[MAXSIZE]; int i, n, position = 0; printf("輸入集合個數："); scanf("%d", &n); printf("n{}"); set[position] = 1; while(1) { printf("n{%d", set[0]); // 印第一個數 for(i = 1; i <= position; i++) printf(",%d", set[i]); printf("}"); if(set[position] < n) { // 遞增集合個數set[position+1] = set[position] + 1; position++; } else if(position != 0) { // 如果不是第一個位置 position--; // 倒退 set[position]++; // 下一個集合尾數 } else // 已倒退至第一個位置 break; } printf("n"); return 0; }
