排列问题

1 排列问题-分治法、递归法

问题描述

R是由n个元素构成的序列集合，R={r1, r2, … ,rn}，求R的全排列perm(R)。

问题分析

  1. 若R中只有1个元素{r}，则perm(R)=(r)
  2. 若R中只有2个元素{r1, r2}，则
    perm(R)=(r1)perm(R1)∪(r2)perm(R2)
    其中，Ri=R-{ri}
  3. 若R中有3个元素{ r1, r2, r3}，则
    perm(R)=(r1)perm(R1)∪(r2)perm(R2)∪(r3)perm(R3)

策略选择

  • 算法思想：分治法

算法设计

  1. 划分：依次将待排列的数组的后n-1个元素与第一个元素交换。
  2. 解决：则每次递归处理的都是后n-1个元素的全排列。
  3. 合并：当数组元素仅有一个时为此递归算法的出口。即开始合并。
1
2
3
4
5
6
7
8
9
10
11
12
算法 perm(Type list[], int k, int m)
//生成列表list的全排列
//输入：一个全排列元素列表list[0..n-1]
//输出：list的全排列集合
if k == m
  for i←0 to m do
    输出list[i]
else
  for i←k to m do
    swap list[k] and list[i]
    perm(list, k+1, m)
    swap list[k] and list[i]

算法分析

$$
T(n)=\begin{cases}
O(1)& n=1\
nT(n-1)+O(1)& n>1
\end{cases}
$$

2 排列问题-Johnson-Trotter Algorithm

算法原理

给一个排列中的每个分量k 赋予一个方向。例如：
$$
\overrightarrow{3}\overleftarrow{2}\overrightarrow{4}\overleftarrow{1}
$$

如果分量k 的箭头指向一个相邻的较小元素，我们说它在这个以箭头标记的排列中是可移动的。３和４是可移动的。

算法过程

1
2
3
4
5
6
7
8
9
JohnsonTrotter(n)
//输入：一个正整数ｎ
//输出：｛１,…,n｝的所有排列的列表
	将第一个排列初始化为
	While 存在可移动整数 do
		求最大的可移动整数k
		把k 和它箭头指向的相邻整数互换
		调转所有大于k 的整数的方向