前言
- 在生成数据的过程中，我们有时候需要基于已有的数据生成排列组合的序列，对此，我们需要编写全排列算法生成序列，本文将分享本人编写的递归实现的全排列算法，支持对任意类型的数据进行生成全排列序列（不局限于数字）
- 全排列： 从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
- 全排列数： f(n)=n!(定义0!=1)f(n)=n!(定义0!=1)
-
递归实现方法：
- 要求长度为n的序列的全排列序列：
- ①依次选取原始序列一个元素作为全排列序列结果的第一个元素
- ②递归调用全排列算法生成剩余n-1个元素的所有全排列序列
- ③将①的元素分别与②的每一个序列组合，即可得到长度为n的序列所有全排列序列
- ④递归结束条件：长度n=2的序列seq的有两个全排列序列为[seq[0],seq[1]]和 [seq[1],seq[0]]
代码
- 输入：长度为n的序列，元素可以任何类型
- 输出：输入序列的所有全排列序列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def full_sort(seq: list): ''' author: 浅若清风cyf date: 2022/03/17 全排列算法（递归） :param seq: 原始序列 :return: ''' results = [] if len(seq) == 1: return seq elif len(seq) == 2: # 递归返回终点 return [[seq[0], seq[1]], [seq[1], seq[0]]] else: for i in seq: sub_seq = seq.copy() # list类型为引用传递，此处需要使用copy()创建一个副本，避免修改原始list sub_seq.remove(i) tmp_result = full_sort(sub_seq) # 获取子列表的全排列 for t in tmp_result: results.append([i] + t) return results |
测试结果
- 测试样例1
|
1
2
3
4
5
6
7
8
9
|
if __name__ == '__main__': res = full_sort([1, 2, 3, 4]) n = 0 for i in res: print(i, end=' ') n += 1 if n % 5 == 0: n = n % 5 print('') |
- 测试样例2
|
1
2
3
4
5
6
7
8
|
res = full_sort(['Apple', 'XiaoMi', 'HuaWei', 'OPPO'])n = 0for i in res: print(i, end=' ') n += 1 if n % 5 == 0: n = n % 5 print('') |
到此这篇关于Python递归生成全排列序列实操的文章就介绍到这了,更多相关Python生成全排列序列内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://juejin.cn/post/7086002435646783502
