Tag Archive for 'partition'

The problem is to enumerate all the ways in which a given number can be written as sum of two or more positive integers. For example 5 can be written as [4, 1], [3, 1, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1], [2, 2, 1] and [3, 2].

I used a recursion to solve the problem. The recursion works like this. Write 5 as 4 + 1. Recurse for 4. 5 can also be written as 3 + 2. Recurse for 3. We are done!

Below is a piece of code written in Java to do the same. I use a map to store pre-computed values. Using the code, I have found the answer for 60. It takes a minute though.

There is this problem on project euler – Problem 76 – which requires one to find the number of ways 100 can be partitioned. Using the above code, I get a heap space error for 100. I suppose instead of enumerating all the ways, to solve the project euler problem, I should try to just count all the possibilities. This might me much quicker.

Here is the java code for the above recursion.

    /**
     * Find all the ways of writing a given number as sum of positive integers
     *
     * @param n the number whose partitions are to be found
     * @return the set of all the partitions of the number
     */
    public static List<List<Integer>> partitionFunction(int n) {
        return NumberRepresentations.partitionFunction(n, 1, new HashMap<Integer, Map<Integer, List<List<Integer>>>>());
    }

    /**
     * Find all the ways of writing a given number as sum of positive integers
     *
     * @param number the number whose partitions are to be found
     * @param minValue the minimum value of any partition number
     * @return the set of all the partitions of the number
     */
    private static List<List<Integer>> partitionFunction(int number, int minValue,
            Map<Integer, Map<Integer, List<List<Integer>>>> preComputedValues) {
        if (preComputedValues.containsKey(number)) {
            List<List<Integer>> prePartitions = preComputedValues.get(number).get(minValue);
            if (prePartitions != null) return prePartitions;
        }

        List<List<Integer>> partitions = new ArrayList<List<Integer>>();
        partitions.add(Arrays.asList(number));
        if (number == 1) return partitions;

        int rightVal;
        for (int leftVal = number - 1; leftVal >= (rightVal = number - leftVal); leftVal--) {
            if (rightVal < minValue) continue;
            for (List<Integer> leftNumbers : NumberRepresentations.partitionFunction(leftVal, rightVal,
                    preComputedValues)) {
                List<Integer> tempList = new ArrayList<Integer>(leftNumbers);
                tempList.add(number - leftVal);
                partitions.add(tempList);
            }
        }

        Map<Integer, List<List<Integer>>> prePartitions = preComputedValues.get(number);
        if (prePartitions == null) preComputedValues.put(number,
                prePartitions = new HashMap<Integer, List<List<Integer>>>());
        prePartitions.put(minValue, partitions);

        return partitions;
    }

Popularity: 6% [?]