当前位置 博文首页 > wang785994599的博客:深度优先搜索之全排列
题目:给定一个字符串"abcde",一个正整数M,求用字符串种M个字符最多可以组成多少种组合?
运用数学思想,很容易算出有多少种,如M=1,RES=5,M=2,RES=20;
思考当前应该怎么做?
从字符串中取出一个,从剩下的字符串中出去一个~~~~~~
M = 2 #M位字符串
my_str = "abcde"
str_list = [x for x in my_str]
used_list = [] #已经使用过的
result = [] #结果集
def dfs(M,step=0):
if step == M:
result.append("".join(used_list))
for i in str_list:#遍历字符串列表
if i not in used_list:#如果该字符未使用
used_list.append(i)#标记为已经使用
dfs(M,step+1) #继续下一步
used_list.remove(i)#本次尝试后,需要取消标记,否则下次无法遍历
if __name__ == '__main__':
dfs(M)
print(result)
?
cs