利用Python內(nèi)置函數(shù)和自己編寫的DFS算法如何實(shí)現(xiàn)排列組合問(wèn)題

第利用Python內(nèi)置函數(shù)和自己編寫的DFS算法，如何實(shí)現(xiàn)排列組合問(wèn)題排列組合是數(shù)學(xué)中的一種常見(jiàn)的計(jì)算方法，用于求出從給定的元素中選取若干個(gè)元素的所有可能的排列或組合。在Python中，有多種方式可以實(shí)現(xiàn)排列組合的計(jì)算。

調(diào)用內(nèi)置函數(shù)

Python標(biāo)準(zhǔn)庫(kù)中提供了一個(gè)模塊itertools，該模塊包含了許多用于生成迭代器的工具函數(shù)，其中就有2個(gè)函數(shù)可以用于計(jì)算排列組合，分別是：

-permutations(p[,r])：從序列p中取出r個(gè)元素的組成全排列，組合得到元組作為新迭代器的元素。

-combinations(p,r)：從序列p中取出r個(gè)元素組成全組合，元素不允許重復(fù)，組合得到元組作為新迭代器的元素。

這2個(gè)函數(shù)都返回一個(gè)迭代器對(duì)象，可以使用list()函數(shù)將其轉(zhuǎn)換為列表，或者使用for循環(huán)遍歷其元素。下面是一個(gè)簡(jiǎn)單的例子：

對(duì)于1到n個(gè)數(shù)進(jìn)行排列，使用內(nèi)置函數(shù)permutations(iterable,r=None)；

permutations(iterable,r=None)連續(xù)返回iterable序列中的元素生成的長(zhǎng)度為r的排列，如果r未指定或者為None，則默認(rèn)值為iterable的長(zhǎng)度。

fromitertoolsimport*

s=[1,2,3,4,5]

forelementinpermutations(s,2):

a=.join(str(element))

print(a,end=)

out[1]:(1,2)(1,3)(1,4)(1,5)(2,1)(2,3)(2,4)(2,5)(3,1)(3,2)(3,4)(3,5)(4,1)(4,2)(4,3)(4,5)(5,1)(5,2)(5,3)(5,4)

如果需要枚舉的數(shù)少的情況，可以直接通過(guò)暴力法

foriinrange(5):

forjinrange(5):

ifi!=j:

print(s[i],s[j])

暴力法對(duì)于數(shù)字少的情況，效果好且簡(jiǎn)單。

對(duì)于1到n個(gè)數(shù)進(jìn)行組合，使用內(nèi)置函數(shù)combinations(iterable,r=None)

In[30]:fromitertoolsimport*

s={1,2,3,4}

forelementincombinations(s,3):

a=.join(str(element))

print(a,end=)

(1,2,3)(1,2,4)(1,3,4)(2,3,4)

自寫算法DFS實(shí)現(xiàn)

除了使用內(nèi)置函數(shù)外，我們也可以自己編寫算法來(lái)實(shí)現(xiàn)排列組合的計(jì)算。一種常見(jiàn)的算法是使用深度優(yōu)先搜索（DFS）來(lái)遍歷所有可能的情況，并將滿足條件的結(jié)果保存下來(lái)。下面是一個(gè)使用DFS實(shí)現(xiàn)全排列和全組合的例子：

a=[1,2,3,4,5]

defdfs(s,t):

ifs==2:

foriinrange(0,2):

print(a[i],end=)

print()

return

foriinrange(s,t+1):

a[s],a[i]=a[i],a[s]

dfs(s+1,t)

a[s],a[i]=a[i],a[s]

dfs(0,4)

上述代碼雖然很短，但有個(gè)缺點(diǎn)就是不能從小到大輸出排列。

改進(jìn)之后的代碼：實(shí)現(xiàn)從小到大輸出

a=[1,2,3,4,5]

b=[0]*10

vis=[0]*20

defdfs(s,t):

ifs==2:

foriinrange(0,2):

print(b[i],end=)

print()

return

foriinrange(0,t):

ifnotvis[i]:

vis[i]=True

b[s]=a[i]

dfs(s+1,t)

vis[i]=False

dfs(0,5)

自寫算法實(shí)現(xiàn)組合：

#首先，我們定義一個(gè)函數(shù)dfs，它接受五個(gè)參數(shù)：

#-cur:當(dāng)前遍歷到的元素的下標(biāo)，初始為0

#-m:要選出的元素個(gè)數(shù)

#-cur_list:保存當(dāng)前已選出的元素的列表

#-original_list:給定的n個(gè)元素的列表

#-result_list:保存最終結(jié)果的列表

defdfs(cur,m,cur_list,original_list,result_list):

#如果已經(jīng)選出了m個(gè)元素，就把當(dāng)前列表添加到結(jié)果列表中，并返回

ifm==0:

result_list.append(list(cur_list))

return

#如果還沒(méi)有選出m個(gè)元素，就從當(dāng)前下標(biāo)開(kāi)始，遍歷原始列表中的每個(gè)元素

foriinrange(cur,len(original_list)):

#把當(dāng)前元素添加到當(dāng)前列表中

cur_list.append(original_list[i])

#遞歸地調(diào)用dfs函數(shù)，更新下標(biāo)和剩余元素個(gè)數(shù)

dfs(i+1,m-1,cur_list,original_list,result_list)

#回溯時(shí)，把當(dāng)前元素從當(dāng)前列表中移除

cur_list.pop()

#然后，我們定義一個(gè)測(cè)試函數(shù)，給定一個(gè)原始列表和一個(gè)目標(biāo)個(gè)數(shù)，調(diào)用dfs函數(shù)，并打印結(jié)果列表

deftest(original_list,m):

#初始化結(jié)果列表為空列表

result_list=[]

#調(diào)用dfs函數(shù)，傳入初始下標(biāo)為0，空的當(dāng)前列表和結(jié)果列表

dfs(0,m,[],original_list,result_list)

#打印結(jié)果列表

print(result_list)

#最后，我們用一個(gè)例子來(lái)測(cè)試一下我們的算法，假設(shè)原始列表為[1,2,3,4]，目標(biāo)個(gè)數(shù)為2

test([1,2,3,4],3)

#輸出結(jié)果