Design and Analysis of Algorithms

218 Design and Analysis of Algorithms

The algorithm print_part() checks that there are no repeated partitions and prints the partition if it is

unique. For small values of n all the three implementations are fast enough, but the real difference is observed

for larger values of n, like 20 or 30.

The fi rst implementation uses a simple approach to storage of the developed partition, in the form of

an array of integers s[ ]. It generates 2

n

− 1 cases and then checks if the partition is unique by insisting that

the summands in the partition are in non-increasing order. For example, while fi nding partitions for n = 5, a

partition (2 1 1 1) is allowed, but (1 2 1 1) will be rejected. The recursive function partition() basically

divides the number ...