全排列quickperm算法的分析

[hit9]

算法的网址：quickperm.org

算法的描述:


>The Counting QuickPerm Algorithm:

let a[] represent an arbitrary list of objects to permute
let N equal the length of a[]
create an integer array p[] of size N to control the iteration
initialize p[0] to 0, p[1] to 0, p[2] to 0, ..., and p[N-1] to 0
initialize index variable i to 1
while (i < N) do {
if (p[i] < i) then {
if i is odd, then let j = p[i] otherwise let j = 0
swap(a[j], a[i])
increment p[i] by 1
let i = 1 (reset i to 1)
} // end if
else { // (p[i] equals i)
let p[i] = 0 (reset p[i] to 0)
increment i by 1
} // end else (p[i] equals i)
} // end while (i < N)


我看不懂官网的解释，求助下，谢谢。

[yyai3]

只能读懂大概的思路～～感觉和TAOCP里面的Algorithm L很像

例如{1,2,3,4,5}，i=2时，{4,5}不动， 列出{1,2,3}的全排列，然后i=3，{5}不动，列出{1,2,3,4}的全排列。

数组p[i]就是为了做局部全排列的，但是不清楚是如何标识的。