partitions

Partitions

Calculate all the additive partitions of a positive number into various denominations. It can be used to solve problems like how many ways are there to give change for $3.50.

Example using 50c, $1 and $2 denominations:

$ partitions 3.50 0.50 1.0 2.0
2.000000 1.000000 0.500000
2.000000 0.500000 0.500000 0.500000
1.000000 1.000000 1.000000 0.500000
1.000000 1.000000 0.500000 0.500000 0.500000
1.000000 0.500000 0.500000 0.500000 0.500000 0.500000
0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000

The denominations don't need to be ordered or unique. We sort them and remove duplicates before generating the partitions. Furthermore, since we use strtod to parse the input, you can give the input in hexadecimal.

$ partitions 3.50 2.0 1.0 0x0.8 1.0 2.0
2.000000 1.000000 0.500000
2.000000 0.500000 0.500000 0.500000
1.000000 1.000000 1.000000 0.500000
1.000000 1.000000 0.500000 0.500000 0.500000
1.000000 0.500000 0.500000 0.500000 0.500000 0.500000
0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000

Caveats

Note that this program is pretty dumb. A smart approach would probably pre-process all the possible partitions into a graph and then iterate over the shortest paths between the root and all the leaves. We just recursively build strings instead. That's right, enjoy your facepalming :) Indeed, you can easily break it by having denominations which are much smaller than the total, because this will generate very long strings as a matter of course, and our sole concession to this is printing a warning.

Furthermore, it would be nice to have better handling of the numerics. We admit doubles, with all the round-off errors which come with them, and we make no attempt to correct them. It would be nice to print the remainder when a partition falls short of total, but due to those same round-off errors we get spurious remainders when this is attempted.

Instead, you can use awk or so if you want to know how much each partition falls short by.

Speaking of awk, we don't make any attempt to format the output "nicely". You can post-process the output if you want something prettier.

Here is an example of partitions working with awk:

$ ./partitions 3.50 0.50 1.0 2.0 | awk '{for(i=1;i<=NF;i++) t+=$i; if(t == 3.50) {for(i=1; i<=NF;i++) printf "%.1f ", $i; printf "\n"}; t=0}'
2.0 1.0 0.5 
2.0 0.5 0.5 0.5 
1.0 1.0 1.0 0.5 
1.0 1.0 0.5 0.5 0.5 
1.0 0.5 0.5 0.5 0.5 0.5 
0.5 0.5 0.5 0.5 0.5 0.5 0.5 

After some post-processing, you can do even more fancy things:

$ ./partitions 3.50 0.50 1.0 2.0 | awk '{for(i=1;i<=NF;i++) t+=$i; if(t == 3.50) {for(i=1; i<=NF;i++) printf "/%.1f", $i; printf "\n"}; t=0}' | tree --fromfile
.
├── 0.5
│   └── 0.5
│       └── 0.5
│           └── 0.5
│               └── 0.5
│                   └── 0.5
│                       └── 0.5
├── 1.0
│   ├── 0.5
│   │   └── 0.5
│   │       └── 0.5
│   │           └── 0.5
│   │               └── 0.5
│   └── 1.0
│       ├── 0.5
│       │   └── 0.5
│       │       └── 0.5
│       └── 1.0
│           └── 0.5
└── 2.0
    ├── 0.5
    │   └── 0.5
    │       └── 0.5
    └── 1.0
        └── 0.5

19 directories, 6 files