Python|有重复元素的排列问题每天一道算法题|算法练习

题目：有重复元素的排列问题

前言
题目要求

问题描述：
算法设计要求：
数据输入：
结果输出：

分析
源代码
输入输出示例
总结

前言这是王晓东所著的《计算机算法设计与分析》（第四版）第二章算法实现题的第5道（P41）
题目要求问题描述：
设集合R={r1,r2,…,r n}是要进行排列的n个元素，其中r1,r2,…,r n可能相同。试着设计一个算法，列出R的所有不同排列。
算法设计要求：
给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。
数据输入：
由文件input.txt提供输入数据，文件的第1行是元素个数n，1<=n<=500。接下来的1行是待排列的n个元素。
结果输出：
程序运行结束时，将计算输出n个元素的所有不同排列到文件output.txt。文件最后一行中的数是排列总数。
分析

这种有重复元素的排列问题可以使用递归来解决。
拿aacc来举例子。
aacc共计四个元素，我们可以将之划分为3个元素的排列。然后再划分为2个，最后只剩单个元素则不用再排列。
举例：
aacc——>aacc——>aacc
很明显，cc也无需排列，则排acc，有acc、cac、cca三种
依次递归即可。

源代码

with open("input5.txt", mode='r') as f1: list1 = f1.read().split() n = int(list1[0]) a = list(list1[1]) b = []def diversal(list, position, end): # 此方法使用递归对有序列表进行调换顺序，从而生成新的排列组合 if position == end:# 如果递归到只剩一个元素 d = list[:] b.append(d)# 将序列自身添加到排列集合中 else: for index in range(position, end):# 做调换 list[index], list[position] = list[position], list[index] diversal(list, position + 1, end)# 递归调用diversal()，使递归向下继续进行 list[index], list[position] = list[position], list[index]diversal(a, 0, n)s = [] # 一个递推式，目的是将b这一排列集合去重。产生的集合s就是没有重复排列的集合了 [s.append(i) for i in b if i not in s] s_len = len(s) with open("output5.txt", mode='w+') as f2: for i in range(s_len):# 最后做将列表转化为字符串的操作，以便符合题目所要求的的输出格式 s[i] = ''.join([j for j in s[i]]) print((str(s[i])), file=f2)print(s.__len__(), file=f2)

输入输出示例 input5.txt