当前位置 博文首页 > wang785994599的博客:深度优先搜索之全排列

    wang785994599的博客:深度优先搜索之全排列

    作者:[db:作者] 时间:2021-09-06 18:59

    题目:给定一个字符串"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