文章目录
文章目录
个人主页：丷从心
系列专栏：分治算法
学习指南：Python学习指南
问题描述
- 设 R = { r 1 , r 2 , ⋯ , r n } R = \set{r_{1} , r_{2} , \cdots , r_{n}} R={r1,r2,⋯,rn}是要进行全排列的 n n n个元素
分治算法
R i = R − { r i } R_{i} = R - \set{r_{i}} Ri=R−{ri}
集合 X X X中的元素的全排列记为 P e r m ( X ) Perm(X) Perm(X)， ( r i ) P e r m ( X ) (r_{i}) Perm(X) (ri)Perm(X)表示在全排列 P e r m ( X ) Perm(X) Perm(X)的每个排列前加上前缀 r i r_{i} ri得到的排列
R R R的全排列可递归定义为
当 n = 1 n = 1 n=1时， P e r m ( R ) = ( r ) Perm(R) = (r) Perm(R)=(r)，其中 r r r是集合 R R R中唯一的元素
当 n > 1 n > 1 n>1时， P e r m ( R ) Perm(R) Perm(R)由 ( r 1 ) P e r m ( R 1 ) (r_{1}) Perm(R_{1}) (r1)Perm(R1)， ( r 2 ) P e r m ( R 2 ) (r_{2}) Perm(R_{2}) (r2)Perm(R2)， ⋯ \cdots ⋯， ( r n ) P e r m ( R n ) (r_{n}) Perm(R_{n}) (rn)Perm(Rn)构成
递归地产生所有前缀是 n u m [ 0 : k − 1 ] num[0 : k - 1] num[0:k−1]，且后缀是 n u m [ k : m ] num[k : m] num[k:m]的全排列的所有排列
Python实现
def permute(nums):
if len(nums) <= 1:
return [nums]
result = []
for i in range(len(nums)):
m = nums[i]
remaining_nums = nums[:i] + nums[i + 1:]
sub_permutations = permute(remaining_nums)
for p in sub_permutations:
result.append([m] + p)
return result
nums = [1, 2, 3]
permutations = permute(nums)
for p in permutations:
print(p)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
