有效地构建总和为数字的排列
Building permutation that sums to a number efficiently
我希望生成更多总和为给定数字 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));
}
}
这可以递归完成。该堆栈包含您之前构建并添加到其中的内容。
虽然我会首先担心正确性，然后才是优化，但我看不出有什么方法可以解决您需要枚举每个 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
您可以使用mapToObj和reduce方法生成指定数字的被加数的可能组合的二维数组，即整数组合 .首先准备二维被加数数组以获得 二维数组流 ，然后依次将这些数组对相乘以获得 笛卡尔积 。
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
如果被加数的顺序很重要，所以 [1,3] 和 [3,1] 不一样，那么它就是 整数组合 。可以使用递归的方法高效构建这个序列，但即便如此，对于大数来说还是太慢了。排列数是2<sup>(n-1)</sup>，所以我停在了27.
tablen=[1-27]的输出，组合数，时间毫秒：
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
Java7代码：
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]
我希望生成更多总和为给定数字 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));
}
}
这可以递归完成。该堆栈包含您之前构建并添加到其中的内容。
虽然我会首先担心正确性，然后才是优化，但我看不出有什么方法可以解决您需要枚举每个 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
您可以使用mapToObj和reduce方法生成指定数字的被加数的可能组合的二维数组，即整数组合 .首先准备二维被加数数组以获得 二维数组流 ，然后依次将这些数组对相乘以获得 笛卡尔积 。
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
如果被加数的顺序很重要，所以 [1,3] 和 [3,1] 不一样，那么它就是 整数组合 。可以使用递归的方法高效构建这个序列，但即便如此，对于大数来说还是太慢了。排列数是2<sup>(n-1)</sup>，所以我停在了27.
tablen=[1-27]的输出，组合数，时间毫秒：
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
Java7代码：
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]