av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術(shù)文章
文章詳情頁

python實現(xiàn)全排列代碼(回溯、深度優(yōu)先搜索)

瀏覽:123日期:2022-08-06 08:40:29

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

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

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

1.1 思想

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

python實現(xiàn)全排列代碼(回溯、深度優(yōu)先搜索)

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),為了進行下一次交換 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)第一個盒子放完后,就該往第二個盒子里放了。假設第一個盒子里放的是arr的第一個數(shù),那么第二個盒子就只能放第2~n個數(shù)了(不能重復)。為此引入visit列表用來標記arr中哪些數(shù)字被使用過了。初始化:

visit = [True, True, True, True]

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

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

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

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

(4)遞歸調(diào)用的一定要注意的問題是遞歸調(diào)用的出口,否則循環(huán)調(diào)用下去程序會崩潰無法運行。在這個問題中什么時候結(jié)束遞歸調(diào)用呢?答案是當這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)。

標簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 人人种亚洲 | 国产精品片aa在线观看 | 久久久久国产精品一区二区 | 九九久久这里只有精品 | 黄色男女网站 | 一级毛片视频 | 成人av鲁丝片一区二区小说 | 黄色国产在线播放 | 国产在线观看 | 国产高清视频 | 91精品久久久久久久久中文字幕 | 精品一区二区电影 | 久久se精品一区精品二区 | 亚洲一二三在线观看 | 在线视频 亚洲 | 国产区视频在线观看 | 日韩av免费看 | 亚洲欧美日韩中文在线 | 免费毛片网| 日韩欧美国产一区二区三区 | 欧美亚洲国产一区二区三区 | 99re热精品视频 | 久草在线| 日韩一区二区三区在线观看 | www.亚洲| 欧美日韩国产在线 | 综合另类| 欧美精品1区2区3区 精品国产欧美一区二区 | 日本三级在线网站 | 日本一二区视频 | 亚洲精品欧美 | 欧美精品首页 | 在线伊人网 | 久久精品国产一区二区电影 | 日日干夜夜操天天操 | 青青草视频网 | 国精日本亚洲欧州国产中文久久 | 国产视频久久久 | 国产免费一区二区 | 国产在线视频一区二区董小宛性色 | 国产亚洲人成a在线v网站 |