轧制多个模具的输出和时间复杂性

Question

我正在处理这个问题，这个问题看起来很棘手：

对于n个骰子，返回所有排列
例如。n=1，输出=[[1]，[2]，[3]，[4]，[5]，[6]
Eg。n=2，输出=[[1,1]，[1,2]，[1,3]，[1,4]，[1,5]，[1,6]，[2,1]。。。。。[6，6]]

所以我使用递归解决了它，当前解决方案使用以前的结果并在此基础上构建：

public class Dice {
private static List<List<Integer>> getCombinations(int n) {
List<List<Integer>> result = new ArrayList<>();
// base cases
if (n == 0) {
return result;
}
if (n == 1) {
for (int i = 1; i <= 6; i++){
List<Integer> list = new ArrayList<>();
list.add(i);
result.add(list);
}
}
// general case
List<List<Integer>> prevResult = getCombinations(n - 1);
for (List<Integer> prevlist: prevResult){
for (int i = 1; i <= 6; i++){
List<Integer> list = new ArrayList<>(prevlist);
list.add(i);
result.add(list);
}
}
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println("val = " + getCombinations(4));
}
}

我想问一下我对时间复杂性的看法是否正确，我认为这将是：

Time Complexity = O(b^d)
where b=branching factor and d=depth of recursion tree
= O(6^n)

这是对的吗？

此外，我还有两个额外的问题：

1. 有没有一种方法可以记住上面的内容来降低时间复杂性
2. 有没有其他更好的算法可以用来解决这个问题

Answer 1

如果您想使用迭代方法而不是递归方法，可以考虑使用Deque:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/** Prints the permutations of rolling N dice with M faces. */
final class DiceRollPermutations {
private DiceRollPermutations() {}
public static void main(String[] args) {
if (args.length != 2) {
System.err.println("Usage: java DiceRollPermutations <numDice> <numFaces>");
System.exit(1);
}
int numDice = Integer.parseInt(args[0]);
int numFaces = Integer.parseInt(args[1]);
Deque<List<Integer>> diceRollPermutations = getDiceRollPermutations(numDice, numFaces);
System.out.printf(
"All possible permutations (%d) for rolling %d %s with %d %s:%n",
diceRollPermutations.size(),
numDice,
numDice == 1 ? "die" : "dice",
numFaces,
numFaces == 1 ? "face" : "faces");
for (List<Integer> permutation : diceRollPermutations) {
System.out.println(permutation);
}
}
public static Deque<List<Integer>> getDiceRollPermutations(int numDice, int numFaces) {
Deque<List<Integer>> permutations = new ArrayDeque<>();
permutations.offer(new ArrayList<Integer>());
for (int i = 1; i <= numDice; i++) {
int numPermutations = permutations.size();
for (int j = 1; j <= numPermutations; j++) {
List<Integer> perm = permutations.pollFirst();
for (int k = 1; k <= numFaces; k++) {
List<Integer> permClone = new ArrayList<>(perm);
permClone.add(k);
permutations.offer(permClone);
}
}
}
return permutations;
}
}

示例用法1:

$ java DiceRollPermutations 2 6
All possible permutations (36) for rolling 2 dice with 6 faces:
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[2, 5]
[2, 6]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[3, 5]
[3, 6]
[4, 1]
[4, 2]
[4, 3]
[4, 4]
[4, 5]
[4, 6]
[5, 1]
[5, 2]
[5, 3]
[5, 4]
[5, 5]
[5, 6]
[6, 1]
[6, 2]
[6, 3]
[6, 4]
[6, 5]
[6, 6]

示例用法2:

$ java DiceRollPermutations 3 6
All possible permutations (216) for rolling 3 dice with 6 faces:
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
[1, 1, 6]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 1]
[1, 4, 2]
[1, 4, 3]
[1, 4, 4]
[1, 4, 5]
[1, 4, 6]
[1, 5, 1]
[1, 5, 2]
[1, 5, 3]
[1, 5, 4]
[1, 5, 5]
[1, 5, 6]
[1, 6, 1]
[1, 6, 2]
[1, 6, 3]
[1, 6, 4]
[1, 6, 5]
[1, 6, 6]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 1, 4]
[2, 1, 5]
[2, 1, 6]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 2, 5]
[2, 2, 6]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 1]
[2, 4, 2]
[2, 4, 3]
[2, 4, 4]
[2, 4, 5]
[2, 4, 6]
[2, 5, 1]
[2, 5, 2]
[2, 5, 3]
[2, 5, 4]
[2, 5, 5]
[2, 5, 6]
[2, 6, 1]
[2, 6, 2]
[2, 6, 3]
[2, 6, 4]
[2, 6, 5]
[2, 6, 6]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 1, 4]
[3, 1, 5]
[3, 1, 6]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 2, 4]
[3, 2, 5]
[3, 2, 6]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
[3, 3, 4]
[3, 3, 5]
[3, 3, 6]
[3, 4, 1]
[3, 4, 2]
[3, 4, 3]
[3, 4, 4]
[3, 4, 5]
[3, 4, 6]
[3, 5, 1]
[3, 5, 2]
[3, 5, 3]
[3, 5, 4]
[3, 5, 5]
[3, 5, 6]
[3, 6, 1]
[3, 6, 2]
[3, 6, 3]
[3, 6, 4]
[3, 6, 5]
[3, 6, 6]
[4, 1, 1]
[4, 1, 2]
[4, 1, 3]
[4, 1, 4]
[4, 1, 5]
[4, 1, 6]
[4, 2, 1]
[4, 2, 2]
[4, 2, 3]
[4, 2, 4]
[4, 2, 5]
[4, 2, 6]
[4, 3, 1]
[4, 3, 2]
[4, 3, 3]
[4, 3, 4]
[4, 3, 5]
[4, 3, 6]
[4, 4, 1]
[4, 4, 2]
[4, 4, 3]
[4, 4, 4]
[4, 4, 5]
[4, 4, 6]
[4, 5, 1]
[4, 5, 2]
[4, 5, 3]
[4, 5, 4]
[4, 5, 5]
[4, 5, 6]
[4, 6, 1]
[4, 6, 2]
[4, 6, 3]
[4, 6, 4]
[4, 6, 5]
[4, 6, 6]
[5, 1, 1]
[5, 1, 2]
[5, 1, 3]
[5, 1, 4]
[5, 1, 5]
[5, 1, 6]
[5, 2, 1]
[5, 2, 2]
[5, 2, 3]
[5, 2, 4]
[5, 2, 5]
[5, 2, 6]
[5, 3, 1]
[5, 3, 2]
[5, 3, 3]
[5, 3, 4]
[5, 3, 5]
[5, 3, 6]
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]
[5, 4, 4]
[5, 4, 5]
[5, 4, 6]
[5, 5, 1]
[5, 5, 2]
[5, 5, 3]
[5, 5, 4]
[5, 5, 5]
[5, 5, 6]
[5, 6, 1]
[5, 6, 2]
[5, 6, 3]
[5, 6, 4]
[5, 6, 5]
[5, 6, 6]
[6, 1, 1]
[6, 1, 2]
[6, 1, 3]
[6, 1, 4]
[6, 1, 5]
[6, 1, 6]
[6, 2, 1]
[6, 2, 2]
[6, 2, 3]
[6, 2, 4]
[6, 2, 5]
[6, 2, 6]
[6, 3, 1]
[6, 3, 2]
[6, 3, 3]
[6, 3, 4]
[6, 3, 5]
[6, 3, 6]
[6, 4, 1]
[6, 4, 2]
[6, 4, 3]
[6, 4, 4]
[6, 4, 5]
[6, 4, 6]
[6, 5, 1]
[6, 5, 2]
[6, 5, 3]
[6, 5, 4]
[6, 5, 5]
[6, 5, 6]
[6, 6, 1]
[6, 6, 2]
[6, 6, 3]
[6, 6, 4]
[6, 6, 5]
[6, 6, 6]