建立有效地求和的排列

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

我有一个用2种情况初始化的地图,其中0是基本情况,而1本身是因为没有要置换的东西。但是,在另一个僵局中,我发现构建利用已解决的排列(n-1)来生成总计为(n)的每个排列的向上排列极为困难。

我将不胜感激任何帮助!我还是个新手,如果这是个简单的问题,请您原谅。但是,这让我很沮丧!

输入(n):4

输出:[[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 Map<Integer, List<List<Integer>>> storageOfPerms;


    public Perm() {
        storageOfPerms= new HashMap<>();
        storageOfPerms.put(0, Arrays.asList(Arrays.asList()));
        storageOfPerms.put(1, Arrays.asList(Arrays.asList(1)));
    }

        private List<List<Integer>> computePerm(int n) {

            // I totally lost it here
            if(n==0){
                return permLookup(0);
            }
            else{
            List<List<Integer>> arr1 = permLookup(n-1);
            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 permLookup(n);

        }

    public List<List<Integer>> permLookup(int n) {

        List<List<Integer>> answer = storageOfPerms.get(n);
        if (answer == null) {
            answer = computePerm(n);
            storageOfPerms.put(n, answer);
        }

        return answer;
    }

    public static void main(String[] args) {
        Perm perm1 = new Perm();

        System.out.println(perm1.permLookup(4));

    }
}
评论