CODEWITHSUNDEEP
java
anon
anon

Reputation:

Permutation of sequence?

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

Upvotes: 3

Views: 1483

Answers (5)

MarcoS
MarcoS

Reputation: 13564

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.

Upvotes: 2

kamaci
kamaci

Reputation: 75127

I designed an approach according to that:

Let's accept that count is 3 at your example. This numbers seems like writing numbers from 0 to maximum count -at base count- with number of count step(_ , _ , _) so:

public static void main(String[] args) {
    startAlgorithm(3);        
}
public static void startAlgorithm(int count){
    int start = 0;
    int max = (int) (Math.pow(count, count) - 1);
    for (int number = start; number <= max; number++) {
        int[] printTo = new int[count];
        int tempNum = number;
        for (int i = 0; i < count; i++) {
            int printInt = tempNum % count;
            printTo[count - i - 1] = printInt;
            tempNum /= count;
        }
        for (int y = 0; y < count; y++) {
            System.out.print(printTo[y]);
        }
        System.out.println();
        start++;
    }
}

This solution works for every number you give as a parameter to your function and exactly prints what you want.

Upvotes: 1

Rogach
Rogach

Reputation: 27200

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. :)

Upvotes: 6

David
David

Reputation: 180

If you want to find all possible permutations for a non-specific length of numbers then you should use a recursive algoritm.

Upvotes: 1

eaj
eaj

Reputation: 2606

Did you look at the wikipedia page on permutations? There's at least one algorithm spelled out there.

Upvotes: 0

Related Questions