array permutations

[mtK]

Hello.
How can I get all permutations in array[]. For example I have:
int[] array = {1, 2, 3};

As result I need:
123
132
213
231
312
321

Can you help me with that? Thanks in advance.

[r035198x]

What have you tried?

[mtK]

This works perfectly with Strings, but I can't and can't get it work with an array. :/

public  static void permutacija(String s) { permutacija("", s); }
private static void permutacija(String prefix, String s) {
     int N = s.length();
     if (N == 0) {
          System.out.println(prefix);
     } else {
          for (int i = 0; i < N; i++)
               permutacija(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
     }
}

[JosAH]

There is a nice iterative algorithm that finds a next permutation given a current one; it finds permutations in lexicographic order (dictionary order), e.g. given the permutation 2, 3, 1 it finds the permutation 3, 1, 2. If the current permutation is 3, 2, 1 there is no next permutation; here's the algoritm:

1) find the largest i such that a[i] < a[i+1]
2) if no such i exists there is no next permutation.
3) find the largest j > i such that a[j] > a[i]; such j always exists
4) swap a[i] and a[j]
5) reverse the elements a[i+1], a[i+2] ... a[n] (all elements to the right of i).

I'm sure you can construct a bit of Java from this pseudo code.

kind regards,

Jos

[toadaly]

Assuming the size of the array is not fixed (if it is, you could just use nested loops), the best way is probably a re-entrant method.