2

Generate all partition of a set

 1 year ago
source link: https://www.geeksforgeeks.org/generate-all-partition-of-a-set//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Generate all partition of a set

zaidkhan15

Given a set A = {1, 2, 3, . . ., n }. It is called a partition of the set A if the following conditions follow: 

  • The union of all the sets is the set A
  • The intersection of any two sets is an empty set

Examples:

Input: n = 3
Output: [{1, 2, 3}], [{1, 2}, {3}], [{1, 3}, {2}], [{1}, {2, 3}], [{1}, {2}, {3}]
Explanation: For the set {1, 2, 3} these are 5 possible partitions [{1, 2, 3}], [{1, 2}, {3}], [{1, 3}, {2}], [{1}, {2, 3}], [{1}, {2}, {3}] 

Input: n = 1
Output: {1}
Explanation: For the set {1} these is 1 possible partitions {1} 

Approach: To solve the problem follow the below idea:

The idea is to use recursion to generate all possible partition of a given set, for each element in the set we will either add it to existing subsets or create a singleton subset and we will repeat this process for all elements in the sets until we have considered all the elements and will print each partition.

Below are the steps for the above approach:

  • Initialize an empty list ans to store all the partitions.
  • Create a recursive function Partition that takes the set, an index, and the list ans as parameters.
  • If the index is equal to the size of the set, then print the partition and return it.
  • Now check if we have considered all the elements in the sets, then push the partition into ans and return.
  • Now add the current element to each subset in the partition and recall the new partition and index values then remove the current subset element.
  • Add the current element as a singleton subset and recall the Partition function with the updated partition and index values.
  • Call the allpartition function with the set as input to generate all partitions for a given set.

Below is the code for the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to print a partition
void printPartition(vector<vector<int> > ans)
{
for (auto i : ans) {
cout << "{ ";
for (auto element : i) {
cout << element << " ";
}
cout << "} ";
}
cout << endl;
}
// Function to generate all partitions
void Partition(vector<int> set, int index,
vector<vector<int> >& ans)
{
// If we have considered all elements
// in the set print the partition
if (index == set.size()) {
printPartition(ans);
return;
}
// For each subset in the partition
// add the current element to it
// and recall
for (int i = 0; i < ans.size(); i++) {
ans[i].push_back(set[index]);
Partition(set, index + 1, ans);
ans[i].pop_back();
}
// Add the current element as a
// singleton subset and recall
ans.push_back({ set[index] });
Partition(set, index + 1, ans);
ans.pop_back();
}
// Function to generate all
// partitions for a given set
void allPartitions(vector<int> set)
{
vector<vector<int> > v;
Partition(set, 0, v);
}
// Main function
int main()
{
// The size of the set
int n = 3;
// Initialize the set as
// {1, 2, ..., n}
vector<int> set(n);
for (int i = 0; i < n; i++) {
set[i] = i + 1;
}
cout << "All partition of the set will be : " << endl;
// Generate all partitions of the set
allPartitions(set);
return 0;
}
Output
All partition of the set will be : 
{ 1 2 3 } 
{ 1 2 } { 3 } 
{ 1 3 } { 2 } 
{ 1 } { 2 3 } 
{ 1 } { 2 } { 3 }

Time Complexity: O(2n), where n is the number of elements
Auxiliary Space: O(2n), where n is the number of elements as we are creating a vector of vectors to store all possible partitions


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK