## 算法描述

### 字典序法

1. 由尾部向前寻找第一个满足`before<after`的元素，并记下其下标low，在本例中即`2`对应`low=0`
2. 从low的后一个元素开始向后寻找最后一个满足`list[high]>list[low]`的元素，并记下其下标high，在本例中即`3`对应`high=2`
3. `list[low]``list[high]`对换，得到`list=[3,4,2,1]`
4. 将下标low之后的所有元素翻转，得到`list=[3,1,2,4]`

## Python实现

### 代码

``````def permutations(n):
indices = list(range(n))
print(indices)
while True:
low_index = n-1
while low_index > 0 and indices[low_index-1] > indices[low_index]:
low_index -= 1
if low_index == 0:
break
low_index -= 1
high_index = low_index+1
while high_index < n and indices[high_index] > indices[low_index]:
high_index += 1
high_index -= 1
indices[low_index], indices[high_index] = indices[
high_index], indices[low_index]
indices[low_index+1:] = reversed(indices[low_index+1:])
print(indices)``````

### 运行

``permutations(4)``

``````[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]``````

## 来自Python Docs的实现

Python中内置了全排列的实现，在itertools库中的permutations()方法，在官方Docs中也介绍了一种字典序生成全排列的方法，这个方法显得更高明，但我还没完全看懂，先贴出来一个简化版本的。

### 代码

``````def permutations(n):
indices = list(range(n))
print(tuple(indices))
cycles = list(range(n, 0, -1))
while n:
for i in reversed(range(n)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
print(tuple(indices))
break
else:
return``````

### 运行

``permutations(4)``

``````(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)``````