生成总数为N的所有数字排列 [英] Generating all permutation of numbers that sums up to N

问题描述

我正在编写一个程序，以创建所有等于和等于给定数字N的所有数字的递归置换.但是，我对如何创建该置换感到困惑.任何见解将不胜感激.

I am writing a program to create a recursive permutation of all numbers<=N that add up to a given number N. However I am at a loss on how to create that permutation. Any insights would be appreciated.

起初，我试图使用分区函数对数字进行划分，然后对每个数字集进行置换，但是我认为这不起作用，最好的方法是在对数字求和时进行递归置换，这超出了我的脑海

At first I was trying to partition the numbers using the partition function and permutate each number set later, however I don't think it would work and the best way is the recursively permutate while summing the numbers which is way over my head.

抱歉，这听起来真是愚蠢.但是我真的不知道.

Sorry if this sounds really dumb. But I really have no idea.

示例:

输入:4

输出:[[4]，[3,1]，[1,3]，[2,2]，[1,1,2]，[1,2,1]，[2,1,1]，[1,1,1,1]]

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

public class Perm{


    public List<List<Integer>> partition(int num, int maxNum, List<List<Integer>> arr, ArrayList<Integer> temp){
        if (num == 0) {
            arr.add((List<Integer>)temp.clone());
            temp.clear();
        }
        else{
            for (int i = Math.min(maxNum, num); i >= 1; i--) {
                temp.add(i);
                System.out.println(temp);
                partition(num-i, i, arr, temp);
            }
        }

        return arr;
    }

}

推荐答案

您非常接近，但是您需要先撤消 temp.add(i)，然后才能继续迭代.使用 Deque 代替 列表 .

You were very close, but you need to undo temp.add(i) before continuing the iteration. That is most easily done using a Deque instead of a List.

这就是我的写法:

public static List<List<Integer>> combosWithSum(int sum) {
    if (sum < 0)
        throw new IllegalArgumentException("Sum cannot be negative: " + sum);
    if (sum == 0)
        return Collections.emptyList();
    List<List<Integer>> result = new ArrayList<>();
    buildCombosWithSum(sum, new ArrayDeque<>(), result);
    return result;
}

private static void buildCombosWithSum(int sum, Deque<Integer> combo, List<List<Integer>> result) {
    for (int num = sum; num > 0; num--) {
        combo.addLast(num);
        if (num == sum)
            result.add(new ArrayList<>(combo));
        else
            buildCombosWithSum(sum - num, combo, result);
        combo.removeLast();
    }
}

测试

combosWithSum(5).forEach(System.out::println);

输出

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

要按问题中显示的顺序获取结果，请在 return result; :

To get the result in the order shown in the question, add the following line before return result;:

result.sort(Comparator.comparingInt(List::size));

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

这篇关于生成总数为N的所有数字排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！