算法设计 —— 生成排列的 Heap 算法

简单介绍

排列组合一直以来都是数学领域的热门研究对象之一,在这里我们关注一个与之相关的“生成全排列”问题。

对于一个有 n 个元素的集合,我们可以很轻松的知道它有 n! ( n 的阶乘)个排列,但是我们要如何才能快速有效的将这 n! 个排列全部找出来呢?

下面我们来用代码实现一个由 B.希普(B.Heap)发明的生成排列算法,它实现过程的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
HeapPermute(n)
//输入:一个正整数 n 和一个全局数组 A[1...n]
//输出:A 中元素的全排列
if n = 1
write A
else
for i <- 1 to n do
HeapPermute(n - 1)
if n is odd //n 为奇数时
swap A[1] and A[n]
else swap A[i] and A[n]

实现代码

最近刚好在重新学 Python ,就没有用 C++ ,而是用 Python 来把这个算法实现了一下,具体解释啥的都写在了注释里,这里就不再详细描述了。

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
'''
实现一个完成“生成排列的Heap算法”的类
使用一个数组A[1...n]进行初始化
最终可以得到A中元素的所有排列
'''
class HeapPermute:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums #输入的数组
self.list = [] #存放所有的排列结果

'''
交换数组内第x个和第y个元素
第x个元素的下标为x-1,第y个元素的下标为y-1
'''
def swap(self, x, y):
temp = self.nums[x-1]
self.nums[x-1] = self.nums[y-1]
self.nums[y-1] = temp

'''
算法实现的具体过程
'''
def permute(self, m):
if m == 1:
self.list.append(self.nums.copy())
else:
for i in range(1,m+1):
self.permute(m - 1) #递归调用
if m%2 == 1: #m为奇数时
self.swap(1, m)
else:
self.swap(i, m)

写一个 main 函数调用上面的类来运行:

1
2
3
4
5
if __name__ == "__main__":
nums = [1,2,3] #这里使用数组[1,2,3]作为示例,可以改为其他的
heap = HeapPermute(nums)
heap.permute(heap.n)
print(heap.list) #输出得到的结果

运行结果

将上面两段代码保存在一个文件中后,运行得到的结果如下:

1
[[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]

成功输出了数组[1,2,3]的所有的排列结果。