Permutation of sequence?

Question

I have a specific amount of numbers. Now I want to somehow display all possible permutations of this sequence.

For example if the amount of numbers is 3, I want to display:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
2 2 1
2 2 2

I have this code to do that where depth is the amount of numbers. Obviously this code isn't working correct. Any hints how to improve?:

    for (int i = 0; i < (depth * depth); i++) {

        path = setPath(depth, path, i);

        print(path);
    }

    private static int[] setPath(int depth, int[] path, int i) {

    for (int j = 1; j <= depth; j++) {

        if (j == 1) {
            path[depth-1] = i%depth;
        } else {
            path[depth-j] = i / ((j-1)*depth);  
        }
    }

    return path;
}

Answer 1

Here is some code:

public static void main(String[] args) throws IOException {
    List<Number> list = new ArrayList<Number>();
    list.add(0);
    list.add(1);
    list.add(2);
    printCombinations(new ArrayList<Number>(), list, 0);
}

public static void printCombinations(List<Number> done, List<Number> numbers, int depth) {
    if (numbers.size() <= depth) {
        System.out.println(done); // replace with something better
    } else {
        for (Number r : numbers) {
            List<Number> newDone = new ArrayList<Number>(done);
            newDone.add(r);
            printCombinations(newDone, numbers, depth + 1);
        }
    }
}

Prints exactly what you asked, for any number of any numbers. :)

Answer 2

You want to print permutations with length 3 of the 3 objects {0, 1, 2} allowing for repetitions. You have 3^3 of such permutations. So, the first problem with your code, is that the loop for (int i = 0; i < (depth * depth); i++) { ... } should actually count from 0 to Math.pow(depth, depth). Then, a couple of remarks on the function setPath(...):

• rather than passing path as a parameter, you'd better create a path and return it
• what you want to do in setPath is convert i into base depth: for example, when i is 12, you want to return [1, 1, 0], and 110 in base 3 (your depth) is 13 in base 10

Here's your code with the changes above:

public static void main(String[] args) {
    int depth = 3;
    for (int i = 0; i < Math.pow(depth, depth); i++) {
        int[] path =  setPath(depth, i);
        System.out.println(Arrays.toString(path));
    }
}

private static int[] setPath(int depth, int i) {
    int[] path = new int[depth];
    int num = i;
    int length = path.length - 1;
    int index = 0;
    while (num != 0) {
        int remainder = num % depth;
        num = num / depth;
        path[length - index] = remainder;
        index++;
    }
    return path;
}

An alternative recursive approach is:

public static void main(String[] args) {
    int depth = 3;
    for (int i = 0; i < Math.pow(depth, depth); i++) {
        System.out.println(pad(convert(i, depth), depth));
    }

}

private static String pad(String s, int b) {
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i <= b - s.length() - 1; i++) sb.append(0);
    sb.append(s);
    return sb.toString();
}

private static String convert(int n, int b) {
    if (n < b)
        return String.valueOf(n);
    else
        return convert(n / b, b) + String.valueOf(n % b);
}

where convert performs the base conversion.

I think you can have a more efficient algorithm which count modulo depth form 0 to depth^depth. I have a similar algorithm for printing the elements of a cartesian product, and your problem is actually equivalent to printing the elements of the cartesian product {0, 1, 2} x {0, 1, 2} x {0, 1, 2}.

I hope this helps.