排列的最小变化算法

Question

我的老师给了我这个生成排列的algorithm，并说这是最小变化算法。问题是我无法正确实现它——它会永远循环下去。这是我的代码：

class Program
{
    private static int[] a;
    private static int[] d;
    private static int[] pos;

    public static void Swap(int[] source, int index1, int index2)
    {
        int temp = source[index1];
        source[index1] = source[index2];
        source[index2] = temp;
    }

    static void Main(string[] args)
    {
        int n = 3;
        a = new int[n + 2];
        d = new int[n + 2];
        pos = new int[n + 2];

        for (int i = 1; i <= n; ++i)
        {
            a[i] = pos[i] = i;
            d[i] = -1;
        }

        int m = 0;
        a[0] = a[n + 1] = n + 1;

        while (m != 1)
        {
            for (int i = 1; i <= n; ++i)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();

            m = n;
            while(a[pos[m]+d[m]] > m)
            {
                d[m] = -d[m];
                m = m - 1;
            }

            Swap(a, a[pos[m]], a[pos[m] + d[m]]);
            Swap(pos, pos[m], pos[a[pos[m]] + d[m]]);
        }

        Console.ReadKey();
    }
}

我正在搜索这个算法并找到另一个 pseudocode，它与第一个略有不同，但它也不起作用。我想用 Steinhaus-Johnson-Trotter 算法或者其他算法，我觉得给定的算法是错误的，但是老师坚持认为它是正确的。

所以有没有错误或者我可以忽略老师并使用我想要的？

Answer 1

我注意到的一件事是交换应该接收索引并且您正在发送要交换的单元格的值：

Swap(a, pos[m], pos[m] + d[m]);
Swap(pos, m, a[pos[m]] + d[m]);

排列的最小变化算法

Minimal change algorithm for permutations

c#

permutation