5

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=

  1 1 1 1
  1 1 2
  2 2
  1 3
  4

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!!

Improve this question

4 Answers 4

Reset to default
24

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

1 1 1 1 
1 1 2 
2 2 
1 3 
4

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);

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

How to work around this method to fill List<int[]> partitions = new ArrayList<>();?
@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<int[]> partitions and pass the empty list on the initial call, 4) change System.out.println(suffix) to partitions.add(suffix)
It didn't work. Arrays are bigger than number. Would you please try it to make sure it works?
@Eftekhari I added a runnable javascript snippet to the answer now. You can do something similar in Java.
4

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, "");
}
Improve this answer

2 Comments

Yep, this way you get rid of the deep recursion and the code is even shorter :) I found the other easier to explain though :)
what is the time complexity of above solution?
2

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))
Improve this answer

Comments

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)
Improve this answer

5 Comments

Can this be modified to include only the partitions with distinct parts?
what do you mean by distinct parts? examples?
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 -> en.m.wikipedia.org/wiki/Partition_(number_theory)
yes sure. just change i-k >= l[0] to i-k > l[0] :)
just to give you idea, my code uses dynamic programming.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.