java - 具有动态变量(天)的排列矩阵，每天应该 "generate"一个 for 循环吗？

Question

我想使用动态变量(天)制作排列矩阵。

我当前的代码有 3 个循环(3 天)，如果我想添加另一天或删除一天，我必须添加/删除一个完整的 for 循环。

public static ArrayList<ArrayList<Integer>> computePermutations(int stops, int days) {
        int maxPerDay = stops - (days - 1);
        ArrayList<ArrayList<Integer>> permutationMatrix = new ArrayList<ArrayList<Integer>>();
        for (int m = 1; m <= maxPerDay; m++) {
            for (int n = 1; n <= maxPerDay; n++) {
                for (int o = 1; o <= maxPerDay; o++) {
                    if (m + n + o == stops) {
                        ArrayList<Integer> possibleSolution = new ArrayList<Integer>(Arrays.asList(m, n, o));
                        permutationMatrix.add(possibleSolution);
                    }
                }
            }
        }
        return permutationMatrix;
    }

我还需要更新行:ArrayList<Integer> possibleSolution = new ArrayList<Integer>(Arrays.asList(m, n, o)); ，因此参数 (m, n, o) 根据天数而变化。

Answer 1

您的问题本质上可以概括如下

If I have to compute the permutation of n elements, do I need n embedded for cycles?

答案是否定的。它可以通过嵌入 n 个循环来解决，您的观察是正确的，但这是没有必要的，也不建议这样做。这种解决方案的问题在于，您的程序将提前假设要排列的项目数量，并且当要排列的元素数量是动态时，将难以处理这种情况。

首先，你需要了解什么是 stack也就是说，这是一个Last In，Ffirst Out(LIFO)数据结构，其中意味着你总是可以将元素推到顶部，但是每当你需要取出一个元素时，你就把它带到顶部。

因此，您需要实现以下内容(我没有享受实际实现的乐趣):

• 您创建了一个空堆栈
• 在其顶部添加 1
• 当你的堆栈不为空时
  • 如果不在最后一个元素，则压入尚未在堆栈中的第一个元素
  • 否则如果你在最后一个元素，那么你就找到了一个新的排列并且
    • 当 stack.top 为 n 或没有 stack.top < i <= n 尚未在堆栈中时，stack.pop
    • 如果堆栈为空，则算法结束
    • 其他
      • 当前<- stack.top
      • stack.push(第一个高于当前且不在栈中的元素)

因此，您可以使用一个主循环，并且在该循环内您只需要一些循环来查找下一个未使用的元素，而不是为每个索引都循环。