fork(1) download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. void solve (set<vector<vector<int>>>& solution, vector<int> inputSet, 
  8. vector<vector<int>>& partitions, vector<int> partition, int n, int i) {
  9. 	int numberOfElements = 0;
  10.     for (int i=0; i<partitions.size(); i++) {
  11.         numberOfElements += partitions[i].size();
  12.     }
  13.     if (numberOfElements == n) {
  14.     	vector<vector<int>> newPartitions = partitions;
  15.         for (int i=0; i<newPartitions.size(); i++) {
  16.             sort (newPartitions[i].begin(), newPartitions[i].end());
  17.         }
  18.         sort(newPartitions.begin(), newPartitions.end());
  19.         solution.insert(newPartitions);
  20.         return;  
  21.     }
  22. 	for (int j=i; j<n; j++) {
  23. 		partition.push_back(inputSet[j]);
  24. 		partitions.push_back(partition);
  25. 		vector<int> partitionNew;
  26. 		solve(solution, inputSet, partitions, partitionNew, n, j+1);
  27. 		partitions.pop_back();
  28. 	}
  29. }
  30.  
  31. void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) {
  32. 	if (i == n) {
  33. 		vector<int> partition;
  34. 		vector<vector<int>> partitions;
  35. 		solve(solution, inputSet, partitions, partition, inputSet.size(), 0);
  36. 		return;
  37. 	}
  38. 	for (int j=i; j<=n; j++) {
  39. 		swap(inputSet[i], inputSet[j]);
  40. 		permute(solution, inputSet, i+1, n);
  41. 		swap(inputSet[i], inputSet[j]);
  42. 	}
  43. }
  44.  
  45. int main() {
  46. 	// your code goes here
  47. 	vector<int> inputSet {1, 1, 2, 3}, partition;
  48. 	int counter = 1;
  49. 	set<vector<vector<int>>> partitions;
  50. 	set<vector<vector<int>>>::iterator it;
  51. 	permute(partitions, inputSet, 0, inputSet.size()-1);
  52. 	for (it = partitions.begin(); it!=partitions.end(); it++) {
  53. 		cout<<"Partitions set "<<counter++<<":"<<endl;
  54. 		for (int i = 0; i<(*it).size(); i++) {
  55. 			for(int j = 0; j<(*it)[i].size(); j++) {
  56. 				cout<<(*it)[i][j]<<" ";
  57. 			}
  58. 			cout<<endl;
  59. 		}
  60. 	}
  61. 	return 0;
  62. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Partitions set 1:
1 
1 
2 
3 
Partitions set 2:
1 
1 
2 3 
Partitions set 3:
1 
1 2 
3 
Partitions set 4:
1 
1 2 3 
Partitions set 5:
1 
1 3 
2 
Partitions set 6:
1 1 
2 
3 
Partitions set 7:
1 1 
2 3 
Partitions set 8:
1 1 2 
3 
Partitions set 9:
1 1 2 3 
Partitions set 10:
1 1 3 
2 
Partitions set 11:
1 2 
1 3
https://ideone.com/x8ALki
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!