java - 递归导致额外的不需要的数据

Question

我正在编写一个模块来处理掷骰子。鉴于 x 死于 y 面，我试图列出所有可能的掷骰组合。

这段代码假设有 3 个骰子，每个骰子有 3 个面，分别标记为 1、2 和 3。(我意识到我使用的是“魔数(Magic Number)”，但这只是为了简化并让基本代码正常工作。)

        int[] set = { 1, 1, 1 };
        list = diceroll.recurse(0,0, list, set);

...

    public ArrayList<Integer> recurse(int index, int i, ArrayList<Integer> list, int[] set){
        if(index < 3){
//          System.out.print("\n(looping on "+index+")\n");
            for(int k=1;k<=3;k++){
//              System.out.print("setting i"+index+" to "+k+" ");
                set[index] = k;
                dump(set);
                recurse(index+1, i, list, set);
            }
        }
        return list;
    }

(dump() 是一个简单的方法，只显示 list[] 的内容。暂时不使用变量 i。)

我正在尝试做的是将列表 [index] 递增 1，逐步遍历列表的整个长度并随着我的进行递增。

这是我的“最佳尝试”代码。这是输出:

粗体输出正是我要找的。我不知道如何摆脱其余的。 (这是假设三个骰子，每个都有 3 个面。使用递归，所以我可以将它放大到任何 x 个有 y 个面的骰子。)

[1][1][1] [1][1][1]

[1][1][1] [1][1][2] [1][1][3] [1][2][3]

[1][2][1] [1][2][2] [1][2][3] [1][3][3]

[1][3][1] [1][3][2] [1][3][3] [2][3][3] [2][1][3]

[2][1][1] [2][1][2] [2][1][3] [2][2][3]

[2][2][1] [2][2][2] [2][2][3] [2][3][3]

[2][3][1] [2][3][2] [2][3][3] [3][3][3] [3][1][3]

[3][1][1] [3][1][2] [3][1][3] [3][2][3]

[3][2][1] [3][2][2] [3][2][3] [3][3][3]

[3][3][1] [3][3][2] [3][3][3]

对于格式，我深表歉意。

如有任何帮助，我们将不胜感激。 (这种方法实际上是为了将数据用于一些非常琐碎的事情，但已经变成了个人挑战。:)

编辑:如果有另一种方法来解决这个问题，我会洗耳恭听，但我也想解决我当前的问题并成功地使用递归来做一些有用的事情。

编辑2:运行代码包括“轻松修复”。当心未使用的变量和奇怪的 hack，我还没有清理它。

package code.testing;

import java.util.ArrayList;

public class CodeTesting {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int[] set = { 1, 1, 1 };
        list = recurse(0,0, list, set);
    }

    public static ArrayList<Integer> recurse(int index, int i, ArrayList<Integer> list, int[] set){
        if(index < 3){
//          System.out.print("\n(looping on "+index+")\n");
            for(int k=1;k<=3;k++){
//              System.out.print("setting i"+index+" to "+k+" ");
                set[index] = k;
                if (index==2){
                    dump(set);
                }
                recurse(index+1, i, list, set);
            }
        }
        return list;
    }

    static void dump(int[] arr) {
        for (int s : arr) {
            System.out.format("[%s]", s);
        }
        System.out.println();
    }
}

Answer 1

很抱歉我不得不重写代码，但它与您的算法几乎相同，只是做了一些更正:

public class DiceRolls {
    static void recurse(int diceNumber, int[] values, final int MAX) {
        if (diceNumber == values.length) {
            System.out.println(java.util.Arrays.toString(values));
        } else {
            for (int v = 1; v <= MAX; v++) {
                values[diceNumber] = v;
                recurse(diceNumber + 1, values, MAX);
            }
        }
    }
    public static void main(String[] args) {
        recurse(0, new int[3], 4);
    }
}

这是一个标准的连音递归生成器。如果要添加所有 int[]进入 List , 然后确保 add(values.clone())所以他们是独立的int[]对象。

---

但是额外的输出是什么？

问题是您在掷完所有骰子之前过早地倾倒。在伪代码中，这就是您正在做的:

if we're not done yet
    trying all possibilities for this dice
       dump result so far // premature dumping!
       recurse for next dice

一个简单的修复代码的方法是执行以下操作:

if we're not done yet
    trying all possibilities for this dice
       recurse for next dice
else, we're done, so
    dump result // timely!

所以回到 Java 实现，修复只是移动了 dump(set);到else if (index < 3) 的案例声明。