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

2021/8/15 11:05:49

本文主要是介绍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:

    输入:[]

    输出:[[]]

    

 

(2)示范2:

    输入:[1,2,3]

    输出:[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

    

 

 5.总结:

 代码量比大佬的多很多,但我觉得够基础。不足之处还望各位指正,让我有所提高。

 



这篇关于C++对一个集合的全子集输出的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程