有效地求和的建筑物置换

Question

我希望产生更多的排列，总和等于给定的数字N，但是这次效率更高。由于采用一般方法，创建永久性排列需要花费永久性。

我有一个地图，其中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 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
                }
                allRPals(n).add(arr2);
            }
            }

            return computePerm(n);

        }


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

        System.out.println(computerPerm(4));

    }
}

Answer 1

这可以递归进行。堆栈包含您先前构建的内容并将其添加到堆栈中。

虽然我先担心正确性，然后再担心优化，但我没有办法解决需要枚举每个integer partitions的事实，因此除非我不这样做，否则复杂度将是指数级的正在丢失某些内容。

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

输出：

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