使用迭代的字符串的所有排列

排列，也称为“排列编号”或“顺序”，是将有序列表S中的元素重新排列成与S本身的一一对应关系。长度为n的字符串有n！排列（来源： 数学单词 )

下面是字符串ABC的排列。 ABC ACB BAC BCA CBA CAB

我们讨论了打印排列的不同递归方法 在这里 和 在这里 .

如何迭代打印所有排列？ A. 简单解决方案 使用n-1个元素的置换生成n个元素的置换。

例如，让我们看看如何使用大小为2的置换生成大小为3的置换。

两个元素的排列是12和21。 三个元素的排列可以通过在大小为2的所有排列中的不同位置插入3来获得。 在12的不同位置插入3将导致1 2 3、1 3 2和3 1 2。 在2 1的不同位置插入3将导致2 1 3、2 3 1和3 2 1。

为了生成大小为四的排列，我们考虑所有以上六个排列的大小三和插入4在每个排列中的不同位置。

一个有效的解决方案是使用 Johnson和Trotter算法 迭代生成所有排列。