Avoid repeating arrays in random permutations in java

Question

I have the following code:

public static void nextPermutationArray(int[] v) {
    int x = 1;
    int y;
    Random r = new Random();
    while (x < v.length) {
        y = x + r.nextInt(v.length - x);
        int temp = v[x];
        v[x] = v[y];
        v[y] = temp;
        x++;
    }
}

public static void main(String[] args) {
    int[] a = new int[]{0, 1, 2, 3};
    nextPermutationArray(a);
    System.out.println(Arrays.toString(a));
    nextPermutationArray(a);
    System.out.println(Arrays.toString(a));
    nextPermutationArray(a);
    System.out.println(Arrays.toString(a));
    nextPermutationArray(a);
    System.out.println(Arrays.toString(a));
}

The program returns me:

0321

0231

0231

0132

My question is: is there any way to edit the method nextPermutationArray to avoid random permutations like 0231. In other words, the method should return 4 unrepeatable elements.

Do you mean an algorithm to find the [lexicographically next permutation](https://stackoverflow.com/questions/352203/generating-permutations-lazily)? — Michael Butscher, Nov 06 '18 at 19:40
@MichaelButscher simply an algorithm that given a array, it is permuted randomly, but that these permutations are not repeated. — alex, Nov 06 '18 at 19:44
This would require to remember the already returned permutations (e.g. in a `HashSet`) and check against them. — Michael Butscher, Nov 06 '18 at 19:47

score 0 · Answer 1 · answered Nov 06 '18 at 19:54

You can store each permutation that has already been returned in a static variable of type int[][]. If you get a result that is already in the array, you can make another permutation. Repeat until you have a new permutation. But be careful, this can make an endless loop if you want to produce more permutations than possible!

score 0 · Answer 2 · answered Nov 06 '18 at 19:56

This should print out all the permutation without storing them in a HashMap or a List

public static boolean nextPermutationArray(int[] a) {
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) {
        i--;
    }
    if (i < 0) {
        return false;
    }
    int j = a.length - 1;
    while (a[i] >= a[j]) {
        j--;
    }
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
    Collections.reverse(Arrays.asList(Arrays.copyOfRange(a, i + 1, a.length)));
    return true;
}

it will return true until there is a premutation to use it run this code

public static void main(String[] args) {
    int[] a = new int[]{0, 1, 2, 3};
    do {
        System.out.println(Arrays.toString(a));
    } while (nextPermutationArray(a));
}

output is

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 3, 1]
[0, 3, 2, 1]
[1, 3, 2, 0]
[2, 3, 1, 0]
[3, 2, 1, 0]

There is a problem: it's not random. If I repeat the execution I end up with the same values, in the same order. — , Nov 06 '18 at 19:58

Avoid repeating arrays in random permutations in java

2 Answers2