Print all unique integer partitions given an integer as input

Question

I was solving a programming exercise and came across a problem over which I am not able to satisfactorily find a solution. The problem goes as follows:

Print all unique integer partitions given an integer as input.
Integer partition is a way of writing n as a sum of positive integers.

for ex: Input=4 then output should be Output=

How should I think about solving this problem? I was wondering about using recursion. Can anyone provide me an algorithm for this question? Or a hint towards solution. any explanation for such kind of problems is welcome. (I am a beginner in programming world) Thank you!!

Vincent van der Weele · Accepted Answer · 2021-09-16T17:39:51.720

I would approach it this way:

First, generalize the problem. You can define a function

printPartitions(int target, int maxValue, string suffix)

with the specification:

Print all integer partitions of target, followed by suffix, such that each value in the partition is at most maxValue

Note that there is always at least 1 solution (provided both target and maxValue are positive), which is all 1s.

You can use this method recursively. So lets first think about the base case:

printPartitions(0, maxValue, suffix)

should simply print suffix.

If target is not 0, you have to options: either use maxValue or not (if maxValue > target there is only one option: don't use it). If you don't use it, you should lower maxValue by 1.

That is:

if (maxValue <= target)
    printPartitions(target-maxValue, maxValue, maxValue + suffix);
if (maxValue > 1)
    printPartitions(target, maxValue-1, suffix);

Combining this all leads to a relatively simple method (coded in Java here and I reordered the statements a little to obtain the very same order as you described):

void printPartitions(int target, int maxValue, String suffix) {
    if (target == 0)
        System.out.println(suffix);
    else {
        if (maxValue > 1)
            printPartitions(target, maxValue-1, suffix);
        if (maxValue <= target)
            printPartitions(target-maxValue, maxValue, maxValue + " " + suffix);
    }
}

You can simply call this as

printPartitions(4, 4, "");

which outputs

You can also choose to first create a list of all solutions and only print afterwards, like this:

function createPartitions(target, maxValue, suffix, partitions) {
  if (target == 0) {
    partitions.push(suffix);
  } else {
    if (maxValue > 1)
      createPartitions(target, maxValue-1, suffix, partitions);
    if (maxValue <= target)
      createPartitions(target-maxValue, maxValue, [maxValue, ...suffix], partitions);
  }
}

const partitions = [];
createPartitions(4, 4, [], partitions);
console.log(partitions);

How to work around this method to fill `List partitions = new ArrayList<>();`? — Eftekhari, Sep 16 '21 at 12:30
@Eftekhari 1) change the type of `suffix` from `String` to `int[]`, 2) change `maxValue + " " suffix` to something adding `maxValue` to the front of `suffix`, 3) add a function parameter `List partitions` and pass the empty list on the initial call, 4) change `System.out.println(suffix)` to `partitions.add(suffix)` — Vincent van der Weele, Sep 16 '21 at 13:30
It didn't work. Arrays are bigger than number. Would you please try it to make sure it works? — Eftekhari, Sep 16 '21 at 13:36
@Eftekhari I added a runnable javascript snippet to the answer now. You can do something similar in Java. — Vincent van der Weele, Sep 16 '21 at 17:40

score 4 · Answer 2 · edited May 23 '17 at 12:02

This is loosely derived from Heuster's approach.

Firstly, note that the last numbers of the output are 1,2,2,3,4. If the last number is 2, the 2nd last numbers are 1,2. This tells me that it might be a good idea have a recursive function with a for-loop generating the string from the back.

The code itself is pretty straight-forward:

Loop from 1 to target, prepending the variable to the suffix, subtracting it from target and recursing.
Also note that each generated string is sorted (which implicitly avoids duplication of output). We get it sorted by simply passing in the last-generated number and looping no further than that number.

Code:

private void printPartitions(int target, int max, String suffix)
{
    if (target == 0)
       System.out.println(suffix);
    else
    {
       for (int i = 1; i <= max && i <= target; i++)
          printPartitions(target - i, i, i + " " + suffix);
    }
}

Caller function:

public void printPartitions(int target)
{
   printPartitions(target, target, "");
}

Yep, this way you get rid of the deep recursion and the code is even shorter :) I found the other easier to explain though :) — Vincent van der Weele, Jul 18 '13 at 16:49

score 2 · Answer 3 · answered Jul 18 '13 at 12:40

The process to enumerate the integer partitions of a number n is recursive. There is a single partition of 0, the empty set (). There is a single partition of 1, the set (1). There are two partitions of 2, the sets (1 1) and (2). There are three partitions of 3, the sets (1 1 1), (1 2) and (3). There are five partitions of 4, the sets (1 1 1 1), (1 1 2), (1 3), (2 2), and (4). There are seven partitions of 5, the sets (1 1 1 1 1), (1 1 1 2), (1 2 2), (1 1 3), (1 4), (2 3) and (5). And so on. In each case, the next-larger set of partitions is determined by adding each integer x less than or equal to n to all the sets formed by the partition of n − x, eliminating any duplicates.

I give code in several languages at my blog. For example, here is my solution in Scheme:

(define (set-cons x xs)
  (if (member x xs) xs
    (cons x xs)))

(define (parts n)
  (if (zero? n) (list (list))
    (let ((xs (list)))
      (do ((x 1 (+ x 1))) ((= x n) (cons (list n) xs))
        (do ((yss (parts (- n x)) (cdr yss))) ((null? yss))
          (set! xs (set-cons (sort < (cons x (car yss))) xs)))))))

> (parts 0)
(())
> (parts 1)
((1))
> (parts 2)
((2) (1 1))
> (parts 3)
((3) (1 1 1) (1 2))
> (parts 4)
((4) (2 2) (1 1 2) (1 1 1 1) (1 3))
> (parts 5)
((5) (2 3) (1 1 3) (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 4))
> (parts 6)
((6) (3 3) (2 2 2) (2 4) (1 1 4) (1 1 2 2) (1 1 1 1 2)
  ((1 1 1 1 1 1) (1 1 1 3) (1 2 3) (1 5))

rnbguy · Answer 4 · 2013-07-18T16:17:57.077

1

here is an algorithm. let me know what you think. tested on python3

def partition(A):
    table = [[[1]]] + [None]*(A-1)
    for i in range(1,A):
        table[i] = [[i+1]]
        for k in range(i):
            table[i].extend([[i-k]+l for l in table[k] if i-k >= l[0]])
    return table[-1]

def print_partition(A):
    for i in reversed(partition(A)): print(*i)

edited Jul 18 '13 at 16:17

answered Jul 18 '13 at 10:59

rnbguy

1,369
1
10
28

Can this be modified to include only the partitions with distinct parts? – Sidharth Samant Mar 04 '17 at 14:46
what do you mean by distinct parts? examples? – rnbguy Mar 04 '17 at 20:13
The partitions for 4 are [4], [3,1], [2,2] and [1,1,1,1]. But the partitions with distinct parts are [4] and [3,1], because the others contain duplicates. See the section about odd parts and distinct parts -> https://en.m.wikipedia.org/wiki/Partition_(number_theory) – Sidharth Samant Mar 05 '17 at 01:27
1

yes sure. just change `i-k >= l[0]` to `i-k > l[0]` :) – rnbguy Mar 05 '17 at 11:00
just to give you idea, my code uses dynamic programming. – rnbguy Mar 05 '17 at 11:05

Print all unique integer partitions given an integer as input

4 Answers4

Linked