数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++程序以词法图形顺序生成给定集合的所有子集
这是以词法图形顺序生成给定集合的所有子集的C++程序。该算法以递增顺序打印给定数组集合中每个长度的所有可能的组合。该算法的时间复杂度为O(n*(2^n))。
算法
Begin For each length ‘i’ GenAllSubset() function is called: 1) In GenAllSubset(), if currLen is more than the reqLen then return. 2) Otherwise, if currLen is equal to reqLen then there will be a new sequence generated, print it. 3) If proceed with a start as ‘true’ and recursively call GenAllSubset() with incremented value of ‘currLen’ and ‘s’. else proceed with a start as ‘false’ and recursively call GenAllSubset() with incremented value of ‘s’. End
示例
#include<iostream>
using namespace std;
void Sorting(int a[], int n) //array sorting {
int i, j, t;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
void GenAllSubset(int a[], int reqLen, int s, int currLen, bool check[], int len) {
if(currLen > reqLen)
return;
else if (currLen == reqLen) {
cout<<"\t";
cout<<"{ ";
for (int i = 0; i < len; i++) {
if (check[i] == true) {
cout<<a[i]<<" ";
}
}
cout<<"}\n";
return;
}
if (s == len) {
return;
}
check[s] = true;
GenAllSubset(a, reqLen, s + 1, currLen + 1, check, len);
check[s] = false;
GenAllSubset(a, reqLen, s + 1, currLen, check, len);
}
int main() {
int i, n;
bool ch[n];
cout<<"Enter the number of element array have: ";
cin>>n;
int arr[n];
cout<<"\n";
for (i = 0; i < n; i++) {
cout<<"Enter "<<i+1<<" element: ";
cin>>arr[i];
ch[i] = false;
}
Sorting(arr, n);
cout<<"\nThe all subset of the given set in the lexicographic order: \n";
cout<<"\t{ }\n";
for(i = 1; i <= n; i++) {
GenAllSubset(arr, i, 0, 0, ch, n);
}
return 0;
}输出
Enter the number of element array have: 6
Enter 1 element:3
Enter 2 element: 2
Enter 3 element: 1
Enter 4 element:7
Enter 5 element:6
Enter 6 element: 5
The all subset of the given set in the lexicographic order:
{ }
{ 1 }
{ 2 }
{ 3 }
{ 5 }
{ 6 }
{ 7 }
{ 1 2 }
{ 1 3 }
{ 1 5 }
{ 1 6 }
{ 1 7 }
{ 2 3 }
{ 2 5 }
{ 2 6 }
{ 2 7 }
{ 3 5 }
{ 3 6 }
{ 3 7 }
{ 5 6 }
{ 5 7 }
{ 6 7 }
{ 1 2 3 }
{ 1 2 5 }
{ 1 2 6 }
{ 1 2 7 }
{ 1 3 5 }
{ 1 3 6 }
{ 1 3 7 }
{ 1 5 6 }
{ 1 5 7 }
{ 1 6 7 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 3 7 }
{ 2 5 6 }
{ 2 5 7 }
{ 2 6 7 }
{ 3 5 6 }
{ 3 5 7 }
{ 3 6 7 }
{ 5 6 7 }
{ 1 2 3 5 }
{ 1 2 3 6 }
{ 1 2 3 7 }
{ 1 2 5 6 }
{ 1 2 5 7 }
{ 1 2 6 7 }
{ 1 3 5 6 }
{ 1 3 5 7 }
{ 1 3 6 7 }
{ 1 5 6 7 }
{ 2 3 5 6 }
{ 2 3 5 7 }
{ 2 3 6 7 }
{ 2 5 6 7 }
{ 3 5 6 7 }
{ 1 2 3 5 6 }
{ 1 2 3 5 7 }
{ 1 2 3 6 7 }
{ 1 2 5 6 7 }
{ 1 3 5 6 7 }
{ 2 3 5 6 7 }
{ 1 2 3 5 6 7 }
更新于： 30-7-2019
348 次浏览
广告