0

我今天在实验室会议上被问到这个问题。

我们可以想象一个包含元素 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 个索引的方法，出于某种原因，我们认为这可能是解决方案：使用第 3 个索引来标记向量中索引 ix 开始或结束的位置。但我们陷入了困境，并决定向 SO 社区寻求建议。

4

1 回答 1

2

一种方法是，对于第一个字符e：

  • 首先递归下一个元素
  • e2然后，对于之后的每个元素e：
    • 交换e和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 现场演示。

于 2013-11-28T18:27:20.080 回答