Partitions of an integer are the different ways of writing the integer as a sum of parts.
The parts can be the set of all integers or some restricted set.
Note: This set does not contain 0 as then there would be infinite partitions.
Example: The partitions of 5, when the parts are 1, 2, 3, 4, 5 are :
Thus there are in total 7 partitions of 5, given this set of parts.
Program for generating all partitions of an integer
class Partition:
result = []
def AllPartitions (self, parts, whole):
print("\nWhole : " + str(whole))
print("Parts : " + " ".join(str(parts)))
print("\n")
# Generate all the valid partitions using parts (each part can be taken multiple times)
# to form the whole
self.Generate(parts, whole, len(parts))
self.result.clear()
# Recursive method to generate all possible partitions.
# This method stores the possible combinations in 'result' while continuously
# decreasing the value of the whole. If the whole is reduced to 0, result will have
# a valid partition.
def Generate (self, parts, whole, sz):
if (whole == 0) :
for num in self.result :
print(num, end=" ")
print("\n")
return
elif (sz <= 0 or whole < 0):
return
# Sum found with the last element included
self.result.append(parts[sz-1]);
self.Generate(parts, whole-parts[sz-1], sz)
# Sum found with last element excluded
# Remove the last element that was added to the list earlier.
self.result.pop()
self.Generate(parts, whole, sz-1)
def main():
p = Partition()
whole = 8
parts = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
p.AllPartitions(parts, whole)
parts.clear()
whole = 16
parts = [ 1, 2, 4 ]
p.AllPartitions(parts, whole)
if __name__ == "__main__":
main()
Output
Whole : 8
Parts : [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]
8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
4 4
4 3 1
4 2 2
4 2 1 1
4 1 1 1 1
3 3 2
3 3 1 1
3 2 2 1
3 2 1 1 1
3 1 1 1 1 1
2 2 2 2
2 2 2 1 1
2 2 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Whole : 16
Parts : [ 1 , 2 , 4 ]
4 4 4 4
4 4 4 2 2
4 4 4 2 1 1
4 4 4 1 1 1 1
4 4 2 2 2 2
4 4 2 2 2 1 1
4 4 2 2 1 1 1 1
4 4 2 1 1 1 1 1 1
4 4 1 1 1 1 1 1 1 1
4 2 2 2 2 2 2
4 2 2 2 2 2 1 1
4 2 2 2 2 1 1 1 1
4 2 2 2 1 1 1 1 1 1
4 2 2 1 1 1 1 1 1 1 1
4 2 1 1 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
#include<iostream>
#include<set>
#include<vector>
using namespace std;
class Partition {
public:
vector<int> result;
vector<vector<int>> allparts;
void AllPartitions (vector<int>& parts, int whole) {
cout << "Whole : " << whole << endl;
cout << "Parts : ";
for(const auto& i : parts)
cout << i << " ";
cout << endl;
// Generate all the valid partitions using parts (each part can be taken multiple times)
// to form the whole
Generate(parts, whole, parts.size());
for (const auto& p : allparts) {
for (const auto& i : p)
cout << i << " ";
cout << endl;
}
cout << endl;
result.clear();
allparts.clear();
}
/* Recursive method to generate all possible partitions.
This method stores the possible combinations in 'result' while continuously
decreasing the value of the whole. If the whole is reduced to 0, result will have
a valid partition.
*/
void Generate (vector<int>& parts, int whole, int sz) {
if (whole == 0) {
allparts.push_back(result);
return;
} else if (sz <= 0 or whole < 0) {
return;
}
// Sum found with the last element included
result.push_back(parts[sz-1]);
Generate(parts, whole-parts[sz-1], sz);
// Sum found with last element excluded
result.pop_back();
Generate(parts, whole, sz-1);
}
};
int main() {
Partition p;
int whole = 8;
vector<int> parts = { 1, 2, 3, 4, 5, 6, 7, 8 };
p.AllPartitions(parts, whole);
whole = 16;
vector<int> parts1 = { 1, 2 , 4 };
p.AllPartitions(parts1, whole);
return 0;
}
Output
Whole : 8
Parts : 1 2 3 4 5 6 7 8
8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
4 4
4 3 1
4 2 2
4 2 1 1
4 1 1 1 1
3 3 2
3 3 1 1
3 2 2 1
3 2 1 1 1
3 1 1 1 1 1
2 2 2 2
2 2 2 1 1
2 2 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Whole : 16
Parts : 1 2 4
4 4 4 4
4 4 4 2 2
4 4 4 2 1 1
4 4 4 1 1 1 1
4 4 2 2 2 2
4 4 2 2 2 1 1
4 4 2 2 1 1 1 1
4 4 2 1 1 1 1 1 1
4 4 1 1 1 1 1 1 1 1
4 2 2 2 2 2 2
4 2 2 2 2 2 1 1
4 2 2 2 2 1 1 1 1
4 2 2 2 1 1 1 1 1 1
4 2 2 1 1 1 1 1 1 1 1
4 2 1 1 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Partition {
private List<Integer> result;
Partition() {
result = new ArrayList<Integer>();
}
public void AllPartitions (List<Integer> parts, int whole) {
System.out.println("\nWhole : " + whole);
System.out.print("Parts : ");
for(Integer i : parts)
System.out.print(i + " ");
System.out.println();
// Generate all the valid partitions using parts (each part can be taken multiple times)
// to form the whole
Generate(parts, whole, parts.size());
result.clear();
}
/* Recursive method to generate all possible partitions.
This method stores the possible combinations in 'result' while continuously
decreasing the value of the whole. If the whole is reduced to 0, result will have
a valid partition.
*/
public void Generate (List<Integer> parts, int whole, int sz) {
if (whole == 0) {
for(Integer i : result)
System.out.print(i + " ");
System.out.println();
return;
} else if (sz <= 0 || whole < 0) {
return;
}
// Sum found with the last element included
result.add(parts.get(sz-1));
Generate(parts, whole-parts.get(sz-1), sz);
// Sum found with last element excluded
// Remove the last element that was added to the list earlier.
result.remove(result.size()-1);
Generate(parts, whole, sz-1);
}
public static void main (String args[]) {
Partition p = new Partition();
int whole = 8;
List<Integer> parts = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
p.AllPartitions(parts, whole);
whole = 16;
List<Integer> parts1 = Arrays.asList(1, 2, 4);
p.AllPartitions(parts1, whole);
}
};
Output
Whole : 8
Parts : 1 2 3 4 5 6 7 8
8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
4 4
4 3 1
4 2 2
4 2 1 1
4 1 1 1 1
3 3 2
3 3 1 1
3 2 2 1
3 2 1 1 1
3 1 1 1 1 1
2 2 2 2
2 2 2 1 1
2 2 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Whole : 16
Parts : 1 2 4
4 4 4 4
4 4 4 2 2
4 4 4 2 1 1
4 4 4 1 1 1 1
4 4 2 2 2 2
4 4 2 2 2 1 1
4 4 2 2 1 1 1 1
4 4 2 1 1 1 1 1 1
4 4 1 1 1 1 1 1 1 1
4 2 2 2 2 2 2
4 2 2 2 2 2 1 1
4 2 2 2 2 1 1 1 1
4 2 2 2 1 1 1 1 1 1
4 2 2 1 1 1 1 1 1 1 1
4 2 1 1 1 1 1 1 1 1 1 1
4 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 1 1
2 2 2 2 2 2 1 1 1 1
2 2 2 2 2 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1