Building permutation that sums to a number efficiently

Question

I am looking to generate more permutation that sums up to a given number N, however this time more efficiently. Since by general methods, it takes forever to create 100+ permutations.

However I'm at another impasses where I find it extremely difficult to build upward permutations that utilized the permutations that are already solved n-1 to generate every permutation that sums to n.

I would greatly appreciate any help! I still a total newbie, so sorry if it seems like an easy question. but this is bending my mind!

Input(n): 4

Output: [[4],[3,1],[1,3],[2,2],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]]

import java.util.*;
import javax.naming.PartialResultException;

public class Perm {
    private List<List<Integer>> computePerm(int n) {
        // I totally lost it here
        if (n == 0) {
            return computePerm(0);
        } else {
            List<Integer> arr2 = new ArrayList<>();
            for (List<Integer> entry : arr1) {
                for (int i = 0; i < entry.size(); i++) {
                    arr2.add(entry.get(i)); // This obviously doesn't work
                }
            }
        }
        return computePerm(n);
    }

    public static void main(String[] args) {
        Perm perm1 = new Perm();
        System.out.println(computePerm(4));
    }
}

Impostume

Does this answer your question? Is there an efficient algorithm for integer partitioning with restricted number of parts? – Chair

Also: Integer Partition in Java, Integer Partitioning in Java, Integer Partition Code Optimization. Those might be better than the dupe since you have a general case where all numbers are permitted, presumably. – Chair

I went over the post you've linked me (very helpful), however in most of the cases that partitions are only created in one order whereas I'm looking to generate other orders too where the numbers are the same but positioning differs. Does this mean I have to permutate every partition case I got independently? – Impostume

How large an n are you hoping to go? I don't see any obvious optimization opportunities but I'm not that familiar with the problem domain. I guess if you use the DP approach to get unique partitions, then permute each result, that might yield some improvement (if that's what you're suggesting), but that seems like a lot of work that pretty much winds up mimicking doing it recursively in terms of total work (I'm not sure). BTW, if you run my solution below, it goes up to n = 23 on my machine then blows up the heap, so it also depends on how you plan to store/use the results. – Chair

I was hoping to get n up to around 100, but that seems pretty much impossible at this point. – Impostume

Maybe this can help? #60347684 – Supererogatory

Answer 1

You can generate a 2d array of possible combinations of the summands of the specified number, i.e. the integer composition, using mapToObj and reduce methods. First prepare the 2D arrays of summands to get a stream of 2D arrays, and then multiply the pairs of these arrays sequentially to get the Cartesian product.

Try it online!

int n = 5;
int[][] composition = IntStream.range(0, n)
        // prepare 2D arrays of summands
        .mapToObj(i -> IntStream.rangeClosed(1, n - i)
                .mapToObj(j -> new int[]{j})
                // Stream<int[][]>
                .toArray(int[][]::new))
        // intermediate output, 2D arrays of summands
        .peek(arr -> System.out.println(Arrays.deepToString(arr)))
        // sequential summation of array pairs, i.e. getting the
        // cartesian product of arrays, up to the given number
        .reduce((arr1, arr2) -> Arrays.stream(arr1)
                // combinations of inner arrays
                .flatMap(row1 -> {
                    // sum of the elements of the first row
                    int sum = Arrays.stream(row1).sum();
                    // if the specified number is reached
                    if (sum == n) return Arrays.stream(new int[][]{row1});
                    // otherwise continue appending summands
                    return Arrays.stream(arr2)
                            // drop those combinations that are greater
                            .filter(row2 -> Arrays.stream(row2).sum() + sum <= n)
                            .map(row2 -> Stream.of(row1, row2)
                                    .flatMapToInt(Arrays::stream).toArray());
                }) // array of combinations
                .toArray(int[][]::new))
        // otherwise an empty 2D array
        .orElse(new int[0][]);

// final output, the integer composition of the specified number
Arrays.stream(composition).map(Arrays::toString).forEach(System.out::println);

Intermediate output, 2D arrays of summands:

[[1], [2], [3], [4], [5]]
[[1], [2], [3], [4]]
[[1], [2], [3]]
[[1], [2]]
[[1]]

Final output, the integer composition of the specified number:

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]

---

^{See also: Integer partition iterative code optimization}

Detainer

Answer 2

If the order of the summands matters, so that [1,3] and [3,1] are not the same, then it is the integer composition. You can use the recursive method to build this sequence efficiently, but even so, it is too slow for large numbers. The number of permutations is 2(n-1), so I stopped at 27.

Output of table n=[1-27], number of combinations, time milliseconds:

n:  1, composition:        1, time:     1
n:  2, composition:        2, time:     0
n:  3, composition:        4, time:     0
n:  4, composition:        8, time:     0
n:  5, composition:       16, time:     0
n:  6, composition:       32, time:     1
n:  7, composition:       64, time:     1
n:  8, composition:      128, time:     2
n:  9, composition:      256, time:     4
n: 10, composition:      512, time:     7
n: 11, composition:     1024, time:    14
n: 12, composition:     2048, time:    24
n: 13, composition:     4096, time:    24
n: 14, composition:     8192, time:     1
n: 15, composition:    16384, time:     3
n: 16, composition:    32768, time:     6
n: 17, composition:    65536, time:    11
n: 18, composition:   131072, time:    22
n: 19, composition:   262144, time:    46
n: 20, composition:   524288, time:    87
n: 21, composition:  1048576, time:   174
n: 22, composition:  2097152, time:   368
n: 23, composition:  4194304, time:   768
n: 24, composition:  8388608, time:  1635
n: 25, composition: 16777216, time:  3040
n: 26, composition: 33554432, time:  9015
n: 27, composition: 67108864, time: 45804

Java 7 code:

public static void main(String[] args) {
    List<List<Integer>> list = composition(4, true);
    for (List<Integer> comb : list)
        System.out.println(comb);

    for (int i = 1; i <= 27; i++) {
        long time = System.currentTimeMillis();
        List<List<Integer>> list1 = composition(i, false);
        time = System.currentTimeMillis() - time;

        System.out.println("n: " + String.format("%2d", i)
                + ", composition: " + String.format("%8d", list1.size())
                + ", time: " + String.format("%5d", time));
    }
}

public static List<List<Integer>> composition(int n, boolean verbose) {
    List<List<Integer>> list = new ArrayList<>();
    composition(n, verbose ? "" : null, list, new ArrayList<Integer>());
    return list;
}

public static void composition(
        int i, String indent, List<List<Integer>> master, List<Integer> holder) {

    if (indent != null && i == 0)
        System.out.println(indent + "i=" + i + "    comb=" + holder);

    if (i == 0) master.add(holder);

    for (int j = i; j >= 1; j--) {
        ArrayList<Integer> temp = new ArrayList<>(holder);
        temp.add(j);
        if (indent != null)
            System.out.println(indent + "i=" + i + ",j=" + j + "  temp=" + temp);
        composition(i - j, indent != null ? indent + "  " : null, master, temp);
    }
}

Output of recursive tree n=4:

i=4,j=4  temp=[4]
  i=0    comb=[4]
i=4,j=3  temp=[3]
  i=1,j=1  temp=[3, 1]
    i=0    comb=[3, 1]
i=4,j=2  temp=[2]
  i=2,j=2  temp=[2, 2]
    i=0    comb=[2, 2]
  i=2,j=1  temp=[2, 1]
    i=1,j=1  temp=[2, 1, 1]
      i=0    comb=[2, 1, 1]
i=4,j=1  temp=[1]
  i=3,j=3  temp=[1, 3]
    i=0    comb=[1, 3]
  i=3,j=2  temp=[1, 2]
    i=1,j=1  temp=[1, 2, 1]
      i=0    comb=[1, 2, 1]
  i=3,j=1  temp=[1, 1]
    i=2,j=2  temp=[1, 1, 2]
      i=0    comb=[1, 1, 2]
    i=2,j=1  temp=[1, 1, 1]
      i=1,j=1  temp=[1, 1, 1, 1]
        i=0    comb=[1, 1, 1, 1]

Output of the list n=4:

[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 3]
[1, 2, 1]
[1, 1, 2]
[1, 1, 1, 1]

Detainer

Answer 3

This can be done recursively. The stack contains what you've previously built and adds onto it.

While I'd worry about correctness first, then optimization, I don't see a way to get around the fact that you'll need to enumerate each of the integer partitions, so the complexity is going to be exponential unless I'm missing something.

import java.util.ArrayDeque;
import java.util.ArrayList;

class Main {
    public static ArrayList<ArrayList<Integer>> partition(int n) {
        var result = new ArrayList<ArrayList<Integer>>();
        partition(n, new ArrayDeque<>(), result);
        return result;
    }

    private static void partition(int n, ArrayDeque<Integer> path, 
                                  ArrayList<ArrayList<Integer>> result) {
        if (n == 0) result.add(new ArrayList<Integer>(path));

        for (int i = 1; i <= n; i++) {
            path.offer(i);
            partition(n - i, path, result);
            path.pop();
        }
    }

    public static void main(String[] args) {
        for (var result : partition(4)) {
            for (int i : result) {
                System.out.print(i + " ");
            }

            System.out.println();
        }
    }
}

Output:

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

Chair