Simpler code for 6.10

#1

I’ve come up with a shorter and in my opinion simpler code for 6.10, although the idea is the same (one cycle at a time).

public static int[] permutateInPlace(int[] a, Integer[] permutation) {

for (int i = 0; i < permutation.length; i++) {
    int m = i;

    while (permutation[m] >= 0) {
        swap(a, i, permutation[m]);
        int temp = permutation[m];
        permutation[m] = permutation[m] - permutation.length;
        m = temp;
    }
}

for (int i = 0; i < permutation.length; i++) {
    permutation[i] = permutation[i] + permutation.length;
}

return a;

}

I used a different logic to solve it.
After we move an element from position i to j, we have element j standing at ith position. We can find out where it should be moved if we look at P[j] and move it there, swapping the elements. Now we have an element that was originally at position P[j] staying at i. To find out where it belongs we look at P[P[j]] and move it there and so on.

0 Likes
#2

Hey damluar,

Great, it looks really good to me as your code actually combine the checks of cyclic permutation together with the visited check. Thanks for this idea and sharing!

0 Likes
#3

Even simpler, if you don’t mind that P is modified:

public void applyPermutation(int[] arr, int[] P) {
    for (int i = 0; i < arr.length; i++) {
        while (i != P[i]) {
            swap(arr, i, P[i]);
            swap(P, i, P[i]);
        }
    }
}
0 Likes
#4

@sourcedelica, really cool solution!

0 Likes