Recursive method for the integer partition algorithm

Question

I need to find one of the possible partitions of a number (N) by the number of elements (M) involved, like this:

Number 4
Partitions
4
3 1
2 2
2 1 1
1 3
1 1 1 1

I need to create a function P(N, M), that would return the following result for the call P(4, 2):

3 1
2 2
1 3

I've created the following methods, but I couldn't find a way to break the lines between each partition:

List<String> partitions;

public String[] partitionWithNElements(int n, int numberOfElements) {
    partitions = new ArrayList<String>();
    partition(n, n, "");

    String[] arrayPartition = null;

    for (int i = 0; i < partitions.size(); i++) {
        arrayPartition = partitions.get(i).split("#");
        if (arrayPartition.length == numberOfElements)
            break;
    }

    return arrayPartition;
}

private void partition(int n, int max, String prefix) {
    if (n == 0) {
        if (prefix.startsWith("#"))
            prefix = prefix.substring(1);

        partitions.add(prefix);
        return;
    }

    for (int i = Math.min(max, n); i >= 1; i--) {
        partition(n - i, i, prefix + "#" + i);
    }
}

Code updated once again. Now I'm using a string to return the elements and I've been able to achieve the expected results, however I'm trying to find a solution without using String to return the partitions, so I won't need to use String split function.

I need to return them at least as a comma separated string, but the best scenario would be to return them as arrays/lists. — juliano.net
– juliano.net, Commented Apr 14, 2014 at 19:33

Zejiang Guo · Accepted Answer · 2014-04-14 19:49:12Z

0

Is it OK to have one more parameter in function partitionWithNElements? This parameter can have type LIST >. So instead of return list, you can directly get it through variable you use.

Function can be: public void partitionWithNElements(int n, int numberOfElements, List > result) { //same thing you did, but push values you find to the result list. }

answered Apr 14, 2014 at 19:49

Zejiang Guo

423 bronze badges

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

2 Comments

Zejiang Guo Over a year ago

Because you used ArrayList in your function, I think you should better not make delete operation on this data structure. ArrayList is implemented with array Object[]. So it is good for you do search on it, but bad to add or delete items.

juliano.net Over a year ago

There is no problem in having one more parameter.

Alex Salauyou · Accepted Answer · 2014-04-14 19:51:57Z

0

Just copy partitions of needed size to another list, and return it.

public List<List<Integer>> partitionWithNElements(int n, int numberOfElements) {
    List<List<Integer>> elements = new ArrayList<List<Integer>>();
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    partition(n, n, elements, null);

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    for (int i = 0; i < elements.size(); i++) {
        if (elements.get(i).size() == numberOfElements) {
            result.add(elements.get(i));
        }
    }

    return result;
}

edited Apr 14, 2014 at 19:51

answered Apr 14, 2014 at 19:45

Alex Salauyou

14.4k5 gold badges48 silver badges70 bronze badges

Collectives™ on Stack Overflow

Recursive method for the integer partition algorithm

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related