排列组合与字符串排列算法解析
取ABCD
从ABCD中，取出五个字母，可以重复，但是需要满足A为偶数次（0也是偶数），输出排列组合的个数。
该程序计算长度为5的组合数，每个位置可以是A(1)、B(2)、C(3)或D(4)，统计其中A出现次数为偶数的组合数量。
def count_combinations(): total = 0 # 统计符合条件的排列总数 def backtrack(index, count_a): nonlocal total # 终止条件：选够5个字母（index从1到5，共5个位置） if index == 6: # 检查A的次数是否为偶数 if count_a % 2 == 0: total += 1 return # 遍历4个选择：1=A，2=B，3=C，4=D for num in range(1, 5): # 如果选的是A，次数+1 new_count = count_a + 1 if num == 1 else count_a backtrack(index + 1, new_count) backtrack(1, 0) # 从第1个位置开始，初始A的次数为0 print(total)
排列字符串（去重）输入一个字符串，输出它所有种排列的可能。输入样例：AAB输出样例：AABABABAA
def string_permutations(): # 1. 获取用户输入的字符串，并去除首尾的空格（避免输入时不小心加了空格影响结果） s = input().strip() # 2. 获取字符串的长度，比如输入"AAB"，n=3 n = len(s) # 3. 创建一个和字符串长度相同的布尔列表，标记字符是否被选中（初始全为False，即都未选中） visited = [False] * n # 4. 初始化一个空列表，用来存储所有生成的排列（包括重复的） permutations = [] # 5. 定义回溯函数：递归生成所有排列 # index：当前正在构建的排列的位置（比如index=0是第一个字符，index=2是第三个字符） # current：当前已经构建好的排列字符串（比如"A"、"AA"、"AAB"） def backtrack(index, current): # 6. 终止条件：如果当前位置等于字符串长度，说明排列已构建完成 if index == n: # 7. 将完整的排列添加到结果列表中 permutations.append(current) # 8. 结束当前递归，回到上一层继续尝试其他字符 return # 9. 遍历所有字符，尝试将每个未被选中的字符加入当前排列 for i in range(n): # 10. 检查第i个字符是否未被选中（避免重复选同一个字符） if not visited[i]: # 11. 标记第i个字符为已选中，防止后续重复使用 visited[i] = True # 12. 递归调用：位置+1，当前排列拼接第i个字符（比如current="A"，s[i]="B"，则变成"AB"） backtrack(index + 1, current + s[i]) # 13. 回溯：撤销选择，将第i个字符标记为未选中，供下一轮循环使用 visited[i] = False # 14. 调用回溯函数，初始状态：位置0，当前排列为空字符串 backtrack(0, "") # 15. 去重+排序： # - set(permutations)：将列表转集合，自动去除重复的排列（集合的元素唯一） # - list(...)：将集合转回列表 # - sorted(...)：对去重后的排列按字母顺序排序（比如AAB、ABA、BAA） unique_perms = sorted(list(set(permutations))) # 16. 遍历去重排序后的排列，逐行输出 for perm in unique_perms: print(perm) # 17. 程序入口：只有当直接运行该脚本时，才执行函数 if __name__ == "__main__": string_permutations()