從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當(dāng)m=n時所有的排列情況叫全排列。

公式：全排列數(shù)f(n)=n!(定義0!=1)

1 遞歸實現(xiàn)全排列（回溯思想）

1.1 思想

舉個例子，比如你要對a,b,c三個字符進(jìn)行全排列，那么它的全排列有abc,acb,bac,bca,cba,cab這六種可能就是當(dāng)指針指向第一個元素a時，它可以是其本身a(即和自己進(jìn)行交換)，還可以和b，c進(jìn)行交換，故有3種可能，當(dāng)?shù)谝粋€元素a確定以后，指針移向第二位置，第二個位置可以和其本身b及其后的元素c進(jìn)行交換，又可以形成兩種排列，當(dāng)指針指向第三個元素c的時候，這個時候其后沒有元素了，此時，則確定了一組排列，輸出。但是每次輸出后要把數(shù)組恢復(fù)為原來的樣子。

1.2 python實現(xiàn)

def permutations(arr, position, end): if position == end: print(arr) else: for index in range(position, end): arr[index], arr[position] = arr[position], arr[index] permutations(arr, position + 1, end) arr[index], arr[position] = arr[position], arr[index] # 還原到交換前的狀態(tài)，為了進(jìn)行下一次交換 arr = [1, 2, 3, 4]permutations(arr, 0, len(arr))

2 深度優(yōu)先搜索（DFS）實現(xiàn)全排列

2.1 思想

定義全排列問題：輸入一個長度為n的列表arr，輸出arr的全排列。

（1）首先可以確定的是，每一種全排列的結(jié)果中包含的列表長度均是n。想象面前有n個空盒子，現(xiàn)在要把這n個數(shù)放到這些空盒子里去，每個盒子只能放一個數(shù)。那么第一個盒子中可以放的選擇是n種，可以使用一個循環(huán)來逐個嘗試。

for index in range(0, len(arr)):temp[position] = arr[index]

（2）第一個盒子放完后，就該往第二個盒子里放了。假設(shè)第一個盒子里放的是arr的第一個數(shù)，那么第二個盒子就只能放第2~n個數(shù)了（不能重復(fù)）。為此引入visit列表用來標(biāo)記arr中哪些數(shù)字被使用過了。初始化：

visit = [True, True, True, True]

這樣，當(dāng)?shù)谝粋€位置已經(jīng)使用過時，就在visit里做標(biāo)記：visit = [False, True, True, True]

因此放第一個盒子的代碼可以改寫如下：

for index in range(0, len(arr)): if visit[index] == True: temp[position] = arr[index] visit[index] = False

（3）當(dāng)?shù)趉個盒子處理完畢后，處理下一個盒子直接調(diào)用dfs(k+1)即可，也就是遞歸調(diào)用。解決了當(dāng)下該如何做，下一步也就知道怎么做了。

（4）遞歸調(diào)用的一定要注意的問題是遞歸調(diào)用的出口，否則循環(huán)調(diào)用下去程序會崩潰無法運行。在這個問題中什么時候結(jié)束遞歸調(diào)用呢？答案是當(dāng)這n個盒子都放滿了，即處理到第n+1個盒子時結(jié)束調(diào)用，同時輸出此時的排列結(jié)果。

2.2 python實現(xiàn)

visit = [True, True, True, True]temp = ['' for x in range(0, 4)] def dfs(position): # 遞歸出口 if position == len(arr): print(temp) return # 遞歸主體 for index in range(0, len(arr)): if visit[index] == True: temp[position] = arr[index] visit[index] = False # 試探 dfs(position + 1) visit[index] = True # 回溯。非常重要 arr = [1, 2, 3, 4]dfs(0)

注釋了“非常重要”的語句是不能省略的，省略后僅出現(xiàn)[1, 2, 3, 4]一條結(jié)果。dfs(k+1)前后的兩條語句分別稱之為試探和回溯。

3 combination和permutations函數(shù)的區(qū)別

permutations方法重在排列：

import itertoolsn=3a=[str(i) for i in range(n)]s=''s=s.join(a)for i in itertools.permutations(s,n): print (’’.join(i)) # 結(jié)果 012021102120201210

combinations方法重在組合：

import itertoolsn=3a=[str(i) for i in range(n)]s=''s=s.join(a)for i in itertools.combinations(s,n): print (’’.join(i)) # 結(jié)果 012

以上這篇python實現(xiàn)全排列代碼(回溯、深度優(yōu)先搜索)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持好吧啦網(wǎng)。