Johnson-Trotter算法生成排列数

排列,一般地,从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(permutation)。特别地,当m=n时,这个排列被称作全排列(all permutation)。
Johnson-Trotter是一种基于最小变换的全排列生成算法。

题目描述

46. permutations

Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Johnson-Trotter算法

我们给每一个排列中的每个元素k赋予一个方向。我们在所讨论的每个元素上画一个箭头来指出它的方向,例如:

$$ \vec 3\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{2} \vec 4\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{1} $$

移动元素

如果元素k的箭头指向一个相邻的较小的元素,我们说它在这个以箭头标记的排列中是移动(mobile)的。例如对于排列 $ \vec 3\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{2} \vec 4\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\leftarrow}$}}{1} $ 来说,3和4是移动的,而2和1不是。通过使用移动元素这个概念,我们可以给出所谓的Johnson-Trotter算法的描述,它也是用来生成排列的。

算法

1
2
3
4
5
6
7
8
9
10
11
//实现用来生成排列的Johnson-Trotter算法
//输入:一个正整数n
//输出:{1, ... , n}的所有排列的列表
将第一个排列初始化为 1 2 .. n (箭头全向左)
while 存在一个移动元素 do
求最大的移动元素k
把k和它箭头指向的相邻元素互换(包括元素值和元素的方向)
调转所有大于k的元素的方向
将新排列添加到列表中

在这里我们对n=3应用该算法,其中最大的移动整数用粗体字表示:
$\overleftarrow 1 \overleftarrow 2 \overleftarrow {\mathbf{3}} $, $\overleftarrow 1 \overleftarrow {\mathbf{3}} \overleftarrow 2 $, $\overleftarrow {\mathbf{3}} \overleftarrow 1 \overleftarrow 2 $, $\overrightarrow {\mathbf{3}} \overleftarrow 2 \overleftarrow 1 $, $\overleftarrow 2 \overrightarrow {\mathbf{3}} \overleftarrow 1 $, $\overleftarrow {\mathbf{2}} \overleftarrow 1 \overrightarrow 3 $

在这里特别要注意的是,算法第二步,交换元素的时,不仅要把元素值换了,还要把这个元素的方向也一起换了(看出一个整体)。

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by Kyle on 2017/10/29.
*/
public class Permutations {
public List<List<Integer>> permute(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> lists = new ArrayList<>();
boolean[] directions = new boolean[nums.length];
Arrays.fill(directions, Boolean.TRUE);
boolean[] mobiles;
List<Integer> list1 = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
list1.add(nums[i]);
}
lists.add(list1);
lableA:
while (true) {
int count = 0;
int max = Integer.MIN_VALUE;
int maxIndex = 0;
mobiles = containMobile(directions, nums);
for (int i = 0; i < nums.length; i++) {
if (mobiles[i]) {
count++;
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
}
}
if (count == 0) {
break lableA;
}
// false right, true left
if (directions[maxIndex] == false) {
int temp = nums[maxIndex + 1];
nums[maxIndex + 1] = nums[maxIndex];
nums[maxIndex] = temp;
boolean d = directions[maxIndex + 1];
directions[maxIndex + 1] = directions[maxIndex];
directions[maxIndex] = d;
} else {
int temp = nums[maxIndex - 1];
nums[maxIndex - 1] = nums[maxIndex];
nums[maxIndex] = temp;
boolean d = directions[maxIndex - 1];
directions[maxIndex - 1] = directions[maxIndex];
directions[maxIndex] = d;
}
// change directions when the element > max
for (int j = 0; j < nums.length; j++) {
if (nums[j] > max) {
directions[j] = !directions[j];
}
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
list.add(nums[i]);
}
lists.add(list);
}
return lists;
}
private boolean[] containMobile(boolean[] directions, int[] nums) {
boolean[] mobiles = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
mobiles[i] = mobile(directions[i], nums, i);
}
return mobiles;
}
private boolean mobile(boolean direction, int[] nums, int index) {
if (direction == false && index != nums.length - 1) {
if (nums[index] > nums[index + 1])
return true;
else
return false;
} else if (direction == true && index != 0) {
if (nums[index] > nums[index - 1])
return true;
else
return false;
} else {
return false;
}
}
@Test
public void test() {
List<List<Integer>> lists = permute(new int[]{0,-1,1});
System.out.println();
}
}