非递归Heap's Permutation算法实现逻辑解析求助

我正在尝试理解非递归版本Heap排列算法的工作原理，已经用Python实现了代码，但搞不懂它生成排列的逻辑。

实现代码 #

def element_swap(str_list, i1, i2):
    last = str_list[i1]
    last_swapee = str_list[i2]
    str_list[i1] = last_swapee
    str_list[i2] = last

def theRealPermuator(str_input):
    generated_permutations = [str_input]
    permute_this = list(str_input)
    length = len(permute_this)
    c = [0 for i in range(length)]
    i = 0
    while i < length:
        if c[i] < i:
            if i%2 == 0:
                element_swap(permute_this, 0, i)
            else:
                element_swap(permute_this, c[i], i)
            generated_permutations.append(''.join(permute_this))
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return generated_permutations

print(theRealPermuator('ABC'))

输出结果 #

['ABC', 'BAC', 'CAB', 'ACB', 'BCA', 'CBA']

核心逻辑解析 #

关键变量说明

• c：计数器数组，长度与输入字符串一致，记录每个位置i已完成的交换次数
• i：当前迭代的索引，控制算法流程走向
• permute_this：实时修改的字符列表，用于生成新排列
• generated_permutations：保存所有生成的排列，初始值为原输入字符串

以输入ABC为例的执行流程模拟

初始状态：

• generated_permutations = ['ABC']
• permute_this = ['A','B','C']
• c = [0, 0, 0]
• i = 0

1. i=0：c[0] < 0不成立，重置c[0]为0，i递增为1
2. i=1：c[1]=0 < 1成立，i是奇数，交换c[1]=0和i=1位置的元素（A和B），得到['B','A','C']，加入结果列表；c[1]变为1，i重置为0
3. i=0：条件不成立，i递增为1
4. i=1：c[1]=1 < 1不成立，重置c[1]为0，i递增为2
5. i=2：c[2]=0 < 2成立，i是偶数，交换0和2位置的元素（B和C），得到['C','A','B']，加入结果列表；c[2]变为1，i重置为0
6. i=0：条件不成立，i递增为1
7. i=1：c[1]=0 <1成立，i是奇数，交换0和1位置的元素（C和A），得到['A','C','B']，加入结果列表；c[1]变为1，i重置为0
8. i=0：条件不成立，i递增为1
9. i=1：c[1]=1 <1不成立，重置c[1]为0，i递增为2
10. i=2：c[2]=1 <2成立，i是偶数，交换0和2位置的元素（A和B），得到['B','C','A']，加入结果列表；c[2]变为2，i重置为0
11. i=0：条件不成立，i递增为1
12. i=1：c[1]=0 <1成立，i是奇数，交换0和1位置的元素（B和C），得到['C','B','A']，加入结果列表；c[1]变为1，i重置为0
13. i=0：条件不成立，i递增为1
14. i=1：c[1]=1 <1不成立，重置c[1]为0，i递增为2
15. i=2：c[2]=2 <2不成立，重置c[2]为0，i递增为3，退出循环

算法核心思想

这个非递归实现本质是用计数器数组c追踪每个位置的交换次数，通过两种规则生成所有排列：

• 当i为偶数时，固定交换第0位和第i位
• 当i为奇数时，交换第c[i]位和第i位

每次交换后记录新排列，并重置i回到开头重新检查所有位置的交换可能性；当某个位置i的计数器c[i]达到i时，说明该位置的所有交换组合已穷尽，重置计数器并处理下一个位置，直到i超出字符串长度，结束算法。

内容的提问来源于stack exchange，提问作者Jahleel Murray