Partitions of an integer

  • Thread starter rsq_a
  • Start date
  • #1
107
1

Main Question or Discussion Point

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?
 
Last edited:

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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.
 
  • #3
107
1
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.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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.
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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 x1 + 2x2 + 3x3 + ... + MxM = 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 x1 + 2x2 + 3x3 + ... + MxM = N - M(M+1)/2​

This one has subtracted one from each entry, so that they start counting at 0 instead of 1.
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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.
 
  • #7
If you don't care about computer cycles then you could use Mathematica (or some other high-level language) and say:

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

Output:

{{1, 9}, {2, 8}, {3, 7}, {4, 6}}
 
  • #8
107
1
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.
 

Related Threads for: Partitions of an integer

  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
1
Views
490
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
Top