Need help with unique integer partitions?

[rsq_a]

This is causing me a bigger headache than I anticipated.

Basically, given an integer N and a number M, I need a list of all the possible integer partitions of N into M parts such that each part is strictly positive and each part is UNIQUE. I don't want repetitions. Just unique ones.

So for example, with N = 10 and M = 2

1 + 9
2 + 8
3 + 7
4 + 6

are the only possibilities.

I tried to write a code to do it, but just ran into huge headaches because of the necessary recursion. With M > 2, you need to worry about systematically shifting the sequence as you go. Can anybody make a suggestion?

 

[Hurkyl]

You forgot 10 = 5 + 5...


What do you mean by "systematically shifting the sequence"?



Anyways, you might want a third variable. You want a function

partitions(N, M, B)

that returns all partitions of N that have exactly M parts, each of which is smaller than B.

 

[rsq_a]

You forgot 10 = 5 + 5...What do you mean by "systematically shifting the sequence"?
Anyways, you might want a third variable. You want a function

partitions(N, M, B)

that returns all partitions of N that have exactly M parts, each of which is smaller than B.

It's not just the number of partitions I want. It's the actual list of elements. Also, I forgot to mention above that I need partitions in which element is repeated only once.

So if I wanted to do m = 4, N = 20, I'd need to do:

Shift the 2-last

1 + 2 + 3 + 14
1 + 2 + 4 + 13
1 + 2 + 5 + 12
...

Shift the 2nd number up

1 + 3 + 4 + 12
1 + 3 + 5 + 11
1 + 3 + 6 + 10
...

Shift the 2nd number up again
1 + 4 + 5 + 10
1 + 4 + 6 + 9
1 + 4 + 7 + 8

Shift the 2nd number up again
1 + 5 + 6 + 8

Shift the 1st number up
2 + 3 + 4 + 11
...And so on. Can someone recommend an easier way to do this in terms of implementation into a program? The above requires some really annoying recursive loops.

 

[Hurkyl]

It's not just the number of partitions I want. It's the actual list of elements. Also, I forgot to mention above that I need partitions in which element is repeated only once.

So if I wanted to do m = 4, N = 20, I'd need to do:

Shift the 2-last

1 + 2 + 3 + 14
1 + 2 + 4 + 13
1 + 2 + 5 + 12
...

Shift the 2nd number up

1 + 3 + 4 + 12
1 + 3 + 5 + 11
1 + 3 + 6 + 10
...

Shift the 2nd number up again
1 + 4 + 5 + 10
1 + 4 + 6 + 9
1 + 4 + 7 + 8

Shift the 2nd number up again
1 + 5 + 6 + 8

Shift the 1st number up
2 + 3 + 4 + 11
...


And so on. Can someone recommend an easier way to do this in terms of implementation into a program? The above requires some really annoying recursive loops.

What's wrong with exactly what you said? No recursion is necessary; each time you want to move to the next partition, you simply work from the end to figure out which number needs to be increased... and I don't see what's so annoying about a recursive implementation of the same method.

 

[Hurkyl]

Oh, by the way, it might be easier to enumerate equivalent things, such as:

The list of all increasing sequences of M-1 numbers whose sum S is less than N - {the last number}​

Or even

The list of all sequences of M positive numbers such that the sum x₁ + 2x₂ + 3x₃ + ... + Mx_M = N​

This latter one is formed by taking the deltas in a partition and reversing the order: e.g. the deltas of the partition (2, 7, 16) would be (2, 5, 9), and reversing would be (9, 5, 2). And you can check 9 + 2*5 + 3*2 = 2 + 7 + 16.

Better yet,

The list of all sequences of M nonnegative numbers such that the sum x₁ + 2x₂ + 3x₃ + ... + Mx_M = N - M(M+1)/2​

This one has subtracted one from each entry, so that they start counting at 0 instead of 1.

 

[Hurkyl]

Generalizing a bit...


Rather than a function that enumerates all partitions, it might be better to write the following function

int next_partition(unsigned int *start, size_t len);

which, assuming that the len-long array start is a partition, will replace it with the next partition, and return 1. (Or return 0 if you're already at the last one)


It might be easier to think through how to write this function properly, and it's probably a lot simpler to use in an actual program.

 

[ExactlySolved]

If you don't care about computer cycles then you could use Mathematica (or some other high-level language) and say:

Input:
f = Function[{n, m},
   Select[Sort /@ IntegerPartitions[n], 
    Length[#] === m && Union@# === # &]
   ];
f[10, 2]

Output:

{{1, 9}, {2, 8}, {3, 7}, {4, 6}}

 

[rsq_a]

Thanks for the help. I finally wrote the code to do it (~30 lines).

Funny. It took me ages to wrap my head around how to use functions of functions in a computer program. First time for everything, I guess.