1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Partitions of an integer

  1. May 10, 2009 #1
    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: May 10, 2009
  2. jcsd
  3. May 10, 2009 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. May 10, 2009 #3
    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.
     
  5. May 10, 2009 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. May 10, 2009 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. May 10, 2009 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. May 10, 2009 #7
    If you don't care about computer cycles then you could use Mathematica (or some other high-level language) and say:

    Code (Text):

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

    Output:

    {{1, 9}, {2, 8}, {3, 7}, {4, 6}}
     
     
  9. May 12, 2009 #8
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Partitions of an integer
  1. Partition theory (Replies: 5)

  2. Square of Integer (Replies: 2)

Loading...