全排列

对于字符串abc,其全排列为abc,acb,bac,bca,cab,cba

算法描述

对字符串求全排列可以简单理解为对字符串的下标求全排列,如abc就是对0 1 2求全排列。

这里采用字典序法求全排列,对于012即按顺序得出012,021,102,120,201,210,其按字典顺序依次排列。

字典序法

对于算法运行时得到的一个排列,如list=[2,4,3,1],如何得到这个排列的下一个排列呢?

  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]

这样就得到了[2,4,3,1]字典序下的后一个排列[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)

参考