recursion resulting in extra unwanted data

Question

I'm writing a module to handle dice rolling. Given x die of y sides, I'm trying to come up with a list of all potential roll combinations.

This code assumes 3 die, each with 3 sides labeled 1, 2, and 3. (I realize I'm using "magic numbers" but this is just an attempt to simplify and get the base code working.)

        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() is a simple method to just display the contents of list[]. The variable i is not used at the moment.)

What I'm attempting to do is increment a list[index] by one, stepping through the entire length of the list and incrementing as I go.

This is my "best attempt" code. Here is the output:

Bold output is what I'm looking for. I can't figure out how to get rid of the rest. (This is assuming three dice, each with 3 sides. Using recursion so I can scale it up to any x dice with y sides.)

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

I apologize for the formatting, best I could come up with.

Any help would be greatly appreciated. (This method was actually stemmed to use the data for something quite trivial, but has turned into a personal challenge. :)

edit: If there is another approach to solving this problem I'd be all ears, but I'd also like to solve my current problem and successfully use recursion for something useful.

edit2: Running code including the "easy fix." Beware unused variables and weird hacks, I haven't cleaned it up yet.

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

Call dump() only when index == 2.

Incidentally, i and list seem unused. And the verb is "recur". :)

Answer 2

I'm sorry I had to rewrite the code, but it's pretty much the same algorithm as yours with some corrections:

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

This is a standard tuplet recursive generator. If you want to add all the int[] into a List, then make sure to add(values.clone()) so they are independent int[] objects.

---

But what's with the extra output?

The problem is that you were dumping prematurely, before you're done throwing all the dices. In pseudocode, this is what you're doing:

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

An easy fix to your code is to do the following:

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

So back to the Java implementation, the fix is merely moving dump(set); to an else case for the if (index < 3) statement.

Answer 3

Here is a non-recursive alternative. Change the two constants to calculate all combinations for different dices and different numbers of dice.

package utils;

public class Dice {
    private static int FACES = 3;
    private static int NUMBER_OF_DICE = 3;

    public static void main(String[] args) {
        int start = createPair(1);
        int end = createPair(FACES);
        for (int i = start; i <= end; i++) {
            String combination = Integer.toString(i, FACES+1);
            if (combination.indexOf('0') < 0)
                System.out.println(combination);
        }
    }

    private static int createPair(int number) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < NUMBER_OF_DICE; i++) {
            sb.append(number);
        }
        return Integer.parseInt(sb.toString(), FACES+1);
    }
}