全排列问题(DFS)

全排列问题(DFS)

这种在看数据结构的时候都会有这种,但是不经常复习的话,还是很容易忘记。 DFS是深度优先search, 比发对树遍历的时候,可以先每一层每一层的进行遍历,也可以先一条路走到底式的进行遍历,一条路走到底式的遍历就是DFS,这在迷宫问题中经常用到,即到了某一个节点的时候有多种选择,每个选择下面又有很多的其它的选择,这时候就适合用DFS来解决。

典例1

字符串的全排列,比如输入abc,返回其所有的全排列。代码如下


def main(s='abc'):

    n = len(s)
    assert n>=1

    if n==1:
        return [s]

    ret = []
    a = [0]*(n+1)
    book = [0]*(n+1)


    def dfs(step):
        # 保存的条件是当所有的字符串都已经放好了
        if step==n+1:
            ret.append(a[1:])

        for i in range(1,n+1):   # 每次都会把所有的字符遍历一次,看看有没有visited, 如果没有就参观.
            if book[i]==0:
                a[step] = s[i-1]
                book[i] = 1

                dfs(step+1)
                book[i] = 0

        return
    dfs(1)
    ret = ["".join(x) for x in ret]  # 刚才是用列表来保存的,现在用字符串
    return ret

print(main())


基本的意思就是用一个book来标记在当前的轮次是否已经被访问过.

如果是数字的话

def main(n):

    assert n>=1

    if n==1:
        return [1]

    ret = []
    a = [0]*(n+1)
    book = [0]*(n+1)

    def dfs(step):
        if step==n+1:
            ret.append(a[1:])

        for i in range(1,n+1):
            if book[i]==0:
                a[step] = i
                book[i] = 1

                dfs(step+1)
                book[i] = 0

        return

    dfs(1)
    return ret

print(main(3))

这个题也可以用递归的办法, 递归的交换两个元素.

def fun():

    def permuteDFS(nums, start):
        # 每次是走到最后的时候才会append
        if start >= len(nums):
            print(nums)

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            permuteDFS(nums, start+1)
            nums[start], nums[i] = nums[i], nums[start]


    permuteDFS(list(range(1,4)), 0)

fun()
~                

如果想要用list保存的话要特别注意了,先来一个错误的写法

def fun2():

    ret = []
    def permuteDFS(nums, start, ret):
        # 每次是走到最后的时候才会append
        if start >= len(nums):
            ret.append(nums)

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            permuteDFS(nums, start+1, ret)
            nums[start], nums[i] = nums[i], nums[start]

    permuteDFS(list(range(1,4)), 0, ret)
    print(ret)
    return ret



上面的是错的,运行出的结果的list里面的都是一样的元素,原因是因为在for的里面,先调换了start与i的元素,然后递归之后,虽然在ret.append(nums) 存的是正确的,但是递归完了之后还有一个交换回来的操作,所以会导致之前存的也会发生变化。

解决办法有两种

ret.append(copy.copy(nums))
ret.append(nums[:])

不过第一种方法要import copy才可以。

递归法2

还可以换一种方法用递归,即其实会发现n个元素的全排列实际上是在(n-1)的基础上再把第一个元素或者最后一个元素给insert到里面去,每次可以insert的位置有n个,所以这也验证了n!=n*(n-1)!.


import copy

def permute(nums):

    if len(nums) == 1:
        return [nums]

    first = nums[0]
    nums = nums[1:]

    words = permute(nums)
    # 然后让first去insert
    ret = []
    for x in words:
        for i in range(len(x)+1):
            x.insert(i, first)
            y = copy.copy(x)  # 如果不copy的话,因为后面又把这个删除了所以没用
            ret.append(y)
            del(x[i])  # 是为了让下一次insert其它的位置

    return ret

print(permute([1,2,3]))


上面的代码有同样的之前说的问题,因为先insert后delete导致实际上是没有操作,所以必须先深copy一份,或者append(x[:])

如果改成字符串的话可以这样

def permuteString(s):
    if len(s) == 1:
        return [s]

    first = s[0]
    s = s[1:]

    words = permuteString(s)
    ret = []
    for x in words:
        for i in range(len(x)+1):
            x = x[:i] + first + x[i:]
            ret.append(x[:])
            x = x[:i] +x[i+1:]
    return ret


print(permuteString("abc"))

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦