（任何语言）使用交换查找向量中元素的所有排列

今天在实验室会议上有人问我这个问题。

我们可以想象一个包含元素 1 ... N - 1、长度为 N 的向量。是否存在生成向量中元素的所有排列或顺序的算法（系统）方法。一种建议的方法是交换随机元素。显然，如果存储所有先前生成的排列以供将来参考，那么这将起作用，但这显然是一种非常低效的方法，无论是在空间方面还是在时间方面。

顺便说一句，这样做的原因是从向量中不允许存在此类元素的特殊位置删除特殊元素（例如为零的元素）。因此，随机方法并不是那么荒谬，但想象一下元素数量很大并且可能的排列数量（使得任何“特殊位置”中没有“特殊元素”）的情况是低的。

我们尝试在 N = 5 的情况下解决这个问题：

x = [1, 2, 3, 4, 5]

首先，交换元素 4 和 5：

x = [1, 2, 3, 5, 4]

然后交换3和5：

x = [1, 2, 4, 5, 3]

然后3和4：

x = [1, 2, 5, 4, 3]

最初我们认为使用两个索引 ix 和 jx 可能是一个可能的解决方案。就像是：

ix = 0;
jx = 0;

for(;;)
{
    ++ ix;

    if(ix >= N)
    {
        ix = 0;
        ++ jx;

        if(jx >= N)
        {
            break; // We have got to an exit condition, but HAVENT got all permutations
        }
    }

    swap elements at positions ix and jx

    print out the elements
}

这适用于 N = 3 的情况。但是，它不适用于更高的 N。我们认为这种方法可能是正确的。我们试图扩展到使用 3 个索引的方法，出于某种原因，我们认为这可能是解决方案：使用第三个索引来标记向量中索引 ix 开始或结束的位置。但我们陷入了困境，决定向 SO 社区寻求建议。

一种方法是，对于第一个角色e:

• 首先递归下一个元素
• Then, for each element e2 after e:
  • Swap e and e2
  • 然后递归下一个元素
  • 并撤消交换

伪代码：

permutation(input, 0)

permutation(char[] array, int start)
    if (start == array.length)
        print array

    for (int i = start; i < array.length; i++)
        swap(array[start], array[i])
        permutation(array, start+1)
        swap(array[start], array[i])

通过该函数的主调用，它将尝试第一个位置的每个字符，然后递归。简单地循环所有字符在这里是可行的，因为我们之后撤消每个交换，因此在递归调用返回后，我们保证回到开始的地方。

然后，对于每个递归调用，它都会尝试第二个位置中的每个剩余字符。等等。

Java 现场演示 https://ideone.com/nwiXoS.