Tuesday, February 2, 2010

Combinatoricslib: generating partitions

In number theory, a partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part.

The partitions of 5 are listed below:
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
2 + 2 + 1
3 + 1 + 1
3 + 2
4 + 1
5

The number of partitions of n is given by the partition function p(n). In number theory, the partition function p(n) represents the number of possible partitions of a natural number n, which is to say the number of distinct (and order independent) ways of representing n as a sum of natural numbers.

This is a code:

// create partition generator of 5
Generator<Integer> partitionGenerator = new PartitionGenerator(5);

// create iterator
Iterator<CombinatoricsVector<Integer>> partitionIterator = partitionGenerator.createIterator();

partitionIterator.first();

// go through the iterator
while (!partitionIterator.isDone()) {
partitionIterator.next();
CombinatoricsVector<Integer> partition = partitionIterator.getCurrentItem();
System.out.println(partitionIterator);
}


And the result



PartitionIterator=[#1, CombinatoricsVector=[[1, 1, 1, 1, 1]], size=5]]
PartitionIterator=[#2, CombinatoricsVector=[[2, 1, 1, 1]], size=4]]
PartitionIterator=[#3, CombinatoricsVector=[[2, 2, 1]], size=3]]
PartitionIterator=[#4, CombinatoricsVector=[[3, 1, 1]], size=3]]
PartitionIterator=[#5, CombinatoricsVector=[[3, 2]], size=2]]
PartitionIterator=[#6, CombinatoricsVector=[[4, 1]], size=2]]
PartitionIterator=[#7, CombinatoricsVector=[[5]], size=1]]





Please read more here http://code.google.com/p/combinatoricslib/

2 comments:

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.