algorithm - 从源排列到目的地的最小移动数

Question

给定 [1...N] 的排列“S”和一个空闲点，因此序列的总长度为 N+1。

只需一步，您就可以将排列中的任何元素与空闲点交换。

您需要找到从“S”到排序的排列序列的最小步数。

Answer 1

如果我理解正确，huck_cussler 的解决方案需要前瞻性搜索应该位于空白处的数字位置。

这里有一个替代解决方案，它不需要前瞻，最多使用 2N 次交换。

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

这是 DAle 测试用例的输出:

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]