我们给定一个从 1 到 n 的数字序列。我们需要生成的序列中的每一个排列，都应该与它前一个的排列仅仅交换序列中的两个相邻元素而不同。示例：
输入 : n = 3
输出 : 123 132 312 321 231 213
输入 : n = 4
输出 : 1234 1243 1423 4123 4132
1432 1342 1324 3124 3142 3412 4312
4321 3421 3241 3214 2314 2341 2431
4231 4213 2413 2143 2134
简单的解决方案
我们可以利用 n-1 个元素的排列来生成 n 个元素的排列。例如，让我们看看如何使用大小为 2 的排列来生成大小为 3 的排列。两个元素的排列是 INLINECODE66386b01 和 INLINECODEa3c1e7ab。通过在所有大小为 2 的排列的不同位置插入 3，可以得到三个元素的排列。在 INLINECODE2703d805 的不同位置插入 3 会得到 INLINECODE6d0cf565，INLINECODE8d9c66f5 和 INLINECODE435e2195。在 INLINECODEc1920710 的不同位置插入 3 会得到 INLINECODEf23cd006，INLINECODE5810bcdb 和 INLINECODE0c6ec7c0。要生成大小为四的排列，我们考虑上述所有六个大小为三的排列，并在每个排列的不同位置插入 4。
Johnson 和 Trotter 算法不需要存储所有大小为 n-1 的排列，也不需要遍历所有较短的排列。相反，它跟踪排列中每个元素的方向。
- 找出特定序列中最大的“可移动”整数。 如果一个定向整数大于它朝向的那个直接邻居，那么它就是可移动的。
- 交换这个可移动整数与其方向指向的相邻整数。
- 反转所有值大于该可移动整值的元素的方向。
- 重复步骤 1，直到序列中没有可移动整数为止。
让我们看看如何生成大小为四的排列。我们首先打印 1 2 3 4。最初所有方向都是从右到左。
<1 <2 <3 <4
所有可移动数字是 2、3 和 4。最大的可移动数字是 4。我们交换 3 和 4。因为 4 是最大的，我们不改变任何方向。
<1 <2 <4 <3
4 是最大的可移动数。我们交换它和 2。
<1 <4 <2 <3
4 是最大的可移动数。我们交换它和 1。
<4 <1 <2 <3 [迭代 #4]
3 是最大的可移动数。我们交换它和 2，并改变更大元素的方向。
4> <1 <3 <2
4 是最大的可移动数。我们交换它和 1。
<3 <2
4 是最大的可移动数。我们交换它和 3。
<1 <2
4 是最大的可移动数。我们交换它和 2。
<1 <3 [迭代 #8]
3 是最大的可移动数。我们交换它和 1，并改变更大元素的方向。
<3 <1 <2 <4
4 是最大的可移动数。我们交换它和 2。
<3 <1 <4 <2
4 是最大的可移动数。我们交换它和 1。
<3 <4 <1 <2
4 是最大的可移动数。我们交换它和 3。
<4 <3 <1 <2 [迭代 #12]
2 是最大的可移动数。我们交换它和 1，并改变更大元素的方向。
4> 3> <2 <1
..接下来以 4 为最大可移动数的三个交换结果是：
3> <2 [迭代 #16]
3 是最大的可移动数。我们交换它和 2，并改变更大元素的方向。
<1 <4
..接下来以 4 为最大可移动数的三个交换结果是：
<4 <1 [迭代 #20]
3 是最大的可移动数。我们交换它和 1，并改变更大元素的方向。
4> <2
..接下来以 4 为最大可移动数的三个交换结果是：
<2 4> [迭代 #24]
此时没有剩余的可移动整数。
下面是该方法的实现。
C++
// CPP program to print all permutations using
// Johnson and Trotter algorithm.
#include
using namespace std;
bool LEFTTORIGHT = true;
bool RIGHTTOLEFT = false;
// Utility functions for finding the
// position of largest mobile integer in a[].
int searchArr(int a[], int n, int mobile)
{
for (int i = 0; i < n; i++)
if (a[i] == mobile)
return i + 1;
}
// To carry out step 1 of the algorithm i.e.
// to find the largest mobile integer.
int getMobile(int a[], bool dir[], int n)
{
int mobile_prev = 0, mobile = 0;
for (int i = 0; i < n; i++) {
// direction 0 represents RIGHT TO LEFT.
if (dir[a[i] – 1] == RIGHTTOLEFT && i != 0) {
if (a[i] > a[i – 1] && a[i] > mobile_prev) {
mobile = a[i];
mobile_prev = mobile;
}
}
// direction 1 represents LEFT TO RIGHT.
if (dir[a[i] – 1] == LEFTTORIGHT && i != n – 1) {
if (a[i] > a[i + 1] && a[i] > mobile_prev) {
mobile = a[i];
mobile_prev = mobile;
}
}
}
if (mobile == 0 && mobile_prev == 0)
return 0;
else
return mobile;
}
// Prints a single permutation
int printOnePerm(int a[], bool dir[],