伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
HeapPermute(n)
//实现生成数组全排列的Heap算法
//输入：数组长度，正整数；数组A
//输出：A的全排列
if n = 1
    write A
else
    for i ←1 to n do
	HeapPermute(n-1)
	if n is odd
	    swap A[1]and A[n]
	else swap A[i]and A[n]

分析：
n = 1时，显然成立；
n = 2时，交换位置输出，显然成立；
n = 3时：

  • 第一次循环，HP（2）将数组前两位排列，第三位不动，有xyz，yxz。然后首位交换，有zxy；
  • 第二次循环，HP（2）再次排列前两位，有zxy，xzy。然后首位交换有yzx；
  • 第三次交换，HP（2）再次排列前两位，有yzx，zyx。最后交换得xyz。
    n=4时：
    四次循环，次次对前三位全排列，共4次……

数学归纳法易证该算法对目标数组进行全排列。

时间效率：
对任意数组进行全排列，共有n（n-1）种可能。即进行n（n-1）次输出。初次输出之前不交换。最后一次输出之后交换。
故进行n（n-1）次交换，所以时间效率为n（n-1）近似为n^2.