Min no of moves from source permutation to destination

Question

You are given a permutation 'S' of [1...N] with one free spot so the total length of the sequence is N+1.

In one move you can swap any element of the permutation with the free spot.

You need to find the min moves to go from 'S' to the sorted sequence of permutation.

Answer 1

If I understand it correctly, huck_cussler's solution requires a lookahead to search for the position of the number that should go where the blank is.

Here's an alternative solution that doesn't require lookahead and uses a maximum of 2N swaps.

static void swapperSort(int[] arr)
{
    int n = arr.length-1;
    for(int i=0, pos=0, space=n; i<n-1;)
    {
        System.out.print(pos + " " + space + " " + Arrays.toString(arr));
        if(arr[pos] == pos+1)
        {
            pos = ++i;
        }
        else 
        {
            System.out.print(" SWAP");
            int idx = arr[pos]-1;
            swap(arr, idx, space); 
            swap(arr, pos, idx);

            int tmp = space;
            space = pos;
            pos = tmp;
        }
        System.out.println();
    }
    System.out.println(Arrays.toString(arr));
}

Here's the output for DAle's test case:

0 6 [2, 1, 4, 3, 6, 5, 0] SWAP
6 0 [0, 2, 4, 3, 6, 5, 1] SWAP
0 6 [1, 2, 4, 3, 6, 5, 0]
1 6 [1, 2, 4, 3, 6, 5, 0]
2 6 [1, 2, 4, 3, 6, 5, 0] SWAP
6 2 [1, 2, 0, 4, 6, 5, 3] SWAP
2 6 [1, 2, 3, 4, 6, 5, 0]
3 6 [1, 2, 3, 4, 6, 5, 0]
4 6 [1, 2, 3, 4, 6, 5, 0] SWAP
6 4 [1, 2, 3, 4, 0, 6, 5] SWAP
4 6 [1, 2, 3, 4, 5, 6, 0]
[1, 2, 3, 4, 5, 6, 0]

Answer 2

First, we need to find all permutation cycles of the permutation.

A permutation cycle is a subset of a permutation whose elements trade places with one another. For example, in the permutation group {4,2,1,3}, (143) is a 3-cycle and (2) is a 1-cycle. Here, the notation (143) means that starting from the original ordering {1,2,3,4}, the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., 1 -> 4 -> 3 -> 1.

Permutation cycles do not intersect and we can count the number of swaps for each cycle independently. Every permutation cycle C with more than one element could be transformed to the sorted state with |C| + 1 swaps with a blank space (blank space will return to its initial position at the end). Consequently, the answer to our problem is the total number of elements in all cycles with more than one element plus the number of such cycles. Note that "total number of elements in all cycles with more than one element" is simply the number of elements that are not at their places in the permutation.

Example:

p = [3, 4, 1, 6, 5, 2, 8, 7] 
cycles = [1, 3], [2, 4, 6], [5], [7, 8] 

We don't need to take into account third cycle with one element.

answer = 7 + 3 = 10

All permutation cycles can be found in O(n), and overall complexity of the algorithm would be O(n).