python|python 之递归与非递归实现全排列 python|recursion

全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列。公式：全排列数f(n)=n!(定义 n 为正整数)
# 给定的元素中，抽取一定数量的元素进行排列，求排列的总数
# 现以26个字母为例，从 a 开始，n 个字母的不同种排列数量为 n！将这 n！种不同排列进行输出1 <= n <= 26

# eg: n == 3 时，输出为： bca cba cab acb bac abc
基本思路
1. a共 1 种情况(1!)
2. ba --> ab# 将 b 插入到已有元素 a 的前后位置共 2 种情况(2!)

3. cba cab --> bca bac acb abc# 将 c 插入到已有元素 ba ab 的前面，中间，后面位置共 6 种情况(3!)
非递归实现
因为需要用到阶乘，所以代码中定义了阶乘函数，并调用

def factorial_recursion(n): if n == 1: return 1 return n * factorial_recursion(n-1)def permutation_for_loop(n, letter): # 初始化一个列表，长度为排列的种数 permutation_list = [0 for i in range(factorial_recursion(n))] # 创建临时列表，用于保存循环中元素的排列情况，初始化保存只有一个元素是的情况 temporary_list = ['a']# 从 2 开始循环，因为只要一个元素的情况已保存 for temp_x in range(2, n+1): # 计数，根据计数来更新列表 permutation_list 数据 count = 0 # for 循环遍历临时列表 temporary_list 获取每一个元素 for temp_i in temporary_list: # for 循环遍历从列表 temporary_list 中取得的每一个元素的子元素 for temp_j in temp_i: # 前缀插入，调用 str.replace() 方法返回一个新的字符串，并更新到 permutation_list 相应的位置，同时计数加 1 permutation_list[count] = temp_i.replace(temp_j, letter[temp_x-1] + temp_j) count += 1 # 完成后缀插入，计数加 1 permutation_list[count] = temp_i + letter[temp_x-1] count += 1 # 更新临时列表 permutation_list temporary_list = permutation_list[:factorial_recursion(temp_x)]# 返回结果 return permutation_list

递归实现，用到了列表的双层推导

def permutation_recursion(n, letter): if n == 1: return [letter[n-1]]# 基例 return [i.replace(j, letter[n]+j) for i in permutation_recursion(n-1, letter) for j in i] \ + [i+letter[n] for i in permutation_recursion(n-1, letter)]# 递归链条，使用列表的双层推导实现列表

列表的双层推导
相当于把双层 for 循环中内层循环的表达式放到最前面，两个 for 循环按顺序写

sentence ='I am learning Python now!' lst = [i for x in sentence for i in x] for i in lst: print(i, end = '.') # >>> I. .a.m. .l.e.a.r.n.i.n.g. .P.y.t.h.o.n. .n.o.w.!.

代码调用测试

letter = 'abcdefghijklmnopqrstuvwxyz'pfl = permutation_for_loop(4, letter).sort() for i in range(len(pfl)): print(pfl[i], end = ' ' if (i+1)%4 != 0 else '\n')print('###########################################')pr = permutation_recursion(4, letter).sort() for i in range(len(pr)): print(pr[i], end = ' ' if (i+1)%4 != 0 else '\n')# 运行结果如下： abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba ########################################### abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba

【python|python 之递归与非递归实现全排列】欢迎评论，给出改进意见!