java - 构建有效求和为数字的排列

Question

我希望生成更多总和为给定数字 N 的排列，但这一次效率更高。因为通过一般方法，创建 100 多个排列需要很长时间。

然而，我又陷入了另一个僵局，我发现利用已经解决的排列 n-1 来构建向上排列极其困难，以生成总和为 n< 的每个排列。/.

我将非常感谢任何帮助!我仍然是一个新手，如果这看起来是一个简单的问题，我很抱歉。但这让我心烦意乱!

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

Answer 1

您可以使用 mapToObj 和 reduce 生成指定数字的加数可能组合的二维数组，即整数组合方法。首先准备二维被加数数组以获得二维数组流，然后将这些数组对依次相乘以获得笛卡尔积。

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

中间输出，二维被加数数组:

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

最终输出，指定数字的整数组合:

[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]

---

^{另请参阅:Integer partition iterative code optimization}