南山小马

南山小马

0%

Johnson-Trotter算法生成排列数

发表于 更新于 分类于 Disqus：

排列，一般地，从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();
    }

}