CODEWITHSUNDEEP
javaalgorithmcombinationsinteger-partition
juliano.net
juliano.net

Reputation: 8177

Recursive method for the integer partition algorithm

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.

Upvotes: 0

Views: 900

Answers (2)

Alex Salauyou
Alex Salauyou

Reputation: 14338

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

Upvotes: 0

Zejiang Guo
Zejiang Guo

Reputation: 42

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. }

Upvotes: 0

Related Questions