建立有效地求和的排列组合 [英] Building permutation that sums to a number efficiently

问题描述

我希望生成更多的排列，这些排列加起来等于给定的数字 N ，但是这次效率更高.由于采用一般方法，因此永远需要创建100多个排列.

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.

但是，我处于另一个僵局，在那里我发现很难建立向上的排列，这些排列使用已经解决了 n-1 的排列来生成总和为 n <的每个排列/code>.

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

推荐答案

如果求和顺序很重要，则 [1,3] 和 [3,1] 不相同，则为整数组成.您可以使用递归方法有效地构建此序列 ，但是即使如此，它对于大量数字还是太慢了.排列的数量是 2 (n-1) ，所以我停在了 27 .

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.

表 n = [1-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 代码:

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

递归树的输出 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]

列表的输出 n = 4 :

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

这篇关于建立有效地求和的排列组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！