C++对一个集合的全子集输出

2021/8/15 11:05:49

编程Tag： 元素集合 int C++ 子集 str arr stInt

本文主要是介绍C++对一个集合的全子集输出，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

大学的时候写过全子集的算法程序，后来再想用时一时又想不起来了，所以干脆重新写一份。

1.算法核心思路：

（1）假设集合元素个数为N，则子集元素个数可以为n = {0，1，2，...，N}。

（2）依次遍历查找拥有n个元素的子集。

（3）从0号元素开始，取集合的i（i = 0 ~ N）号元素作为子集的第一个元素，取集合的j（j = i ~ N）号元素作为子集的第二个元素，依次取到n个元素。

2.举例：

如集合[1，2，3]，

0个元素的子集：[]；

1个元素的子集：[1]，[2]，[3]；

2个元素的子集：[1，2]，[1，3]，[2，3]；

3个元素的子集：[1，2，3]。

所以集合[1，2，3]的全部子集为[[]，[1]，[2]，[3]，[1，2]，[1，3]，[2，3]，[1，2，3]]。

3.代码实现：

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<stack>
  5 using namespace std;
  6 
  7 //用类的原因：利用析构函数自动释放指针，避免造成内存泄露（1.代码忘记释放指针；2.因发生异常而没有释放指针）.
  8 class Array {
  9 public:
 10     int* arr;
 11     ~Array()
 12     {
 13         delete[] arr;
 14     }
 15 };
 16 
 17 vector<int> veInt;//用vector容器存放每一个非空子集
 18 vector<int>::iterator itVec;
 19 
 20 void FuncNextChoice(int* arr, int length, int m, int n, int N)
 21 {
 22     int i = m, t = n;
 23 
 24     if (t <= 0)
 25     {
 26         if (veInt.size() == N)
 27         {
 28             cout << '[';
 29             //N==0 表示空子集
 30             if (N != 0)
 31             {
 32                 //非空子集的输出
 33                 for (itVec = veInt.begin(); itVec != veInt.end(); itVec++)
 34                 {
 35                     cout << *itVec;
 36                     ++itVec;
 37                     if (itVec != veInt.end())
 38                     {
 39                         cout << ',';
 40                     }
 41                     --itVec;
 42                 }
 43             }
 44             cout << ']';
 45 
 46             if (length != N)
 47             {
 48                 cout << ',';
 49             }
 50         }
 51     }
 52     else
 53     {
 54         //遍历每一个子集
 55         for (i = m; i < length; i++)
 56         {
 57             if ((i + t) > length)
 58             {
 59                 break;
 60             }
 61             else
 62             {
 63                 veInt.push_back(arr[i]);
 64                 --t;
 65                 FuncNextChoice(arr, length, i + 1, t, N);
 66                 veInt.pop_back();
 67                 ++t;
 68             }
 69         }
 70     }
 71 }
 72 
 73 void FuncOutput(string str)
 74 {
 75     stack<int> stInt;
 76     int i = 0, num = 0, sum = 0, sign = 1, len = 0;
 77 
 78     //str.length()==2 表示集合为空集[].
 79     if (str.length() > 2)
 80     {
 81         //集合元素入栈
 82         for (i = str.length() - 2; i >= 0; i--)
 83         {
 84             if ((str[i] == ',') || (str[i] == '['))
 85             {
 86                 stInt.push(sum);
 87                 sign = 1;
 88                 sum = 0;
 89             }
 90             else
 91             {
 92                 num = str[i] - 48;    // ASSIC 中‘0’的十进制为48
 93                 sum += num * sign;
 94                 sign *= 10;
 95             }
 96         }
 97     }
 98 
 99     len = stInt.size();
100     //int* array = new int[len];
101     Array a;
102     a.arr = new int[len];
103 
104     i = 0;
105     while (!stInt.empty())
106     {
107         //array[i++] = stInt.top();
108         a.arr[i] = stInt.top();
109         i++;
110         stInt.pop();
111     }
112 
113     cout << "[";
114 
115     for (i = 0; i <= len; i++)
116     {
117         //FuncNextChoice(array, len, 0, i, i);
118         FuncNextChoice(a.arr, len, 0, i, i);
119     }
120     cout << ']' << endl;
121 }
122 
123 int main()
124 {
125     string str;
126 
127     while (getline(cin, str, '\n'))
128     {
129         if ((str[0] == '[') && (str[str.length() - 1] == ']'))
130         {
131             try {
132                 FuncOutput(str);
133             }
134             catch (...)
135             {
136                 cout << "Error!" << endl;
137             }
138         }
139         else
140         {
141             cout << "Input error!" << endl;
142         }
143     }
144 
145     return 0;
146 }

4.输入输出示范：

（1）示范1：

　　输入：[]

　　输出：[[]]