問(wèn)題描述：

給定一個(gè)包含n個(gè)元素的列表，從中選擇m個(gè)元素作為一個(gè)子列表，求解所有可能的子列表。

例如：

一個(gè)列表是[1，2，3，4]，從中任選3個(gè)數(shù)作為一個(gè)子列表。

則所有可能的子列表為：[1,2,3], [1,2,4], [1,3,4], [2,3,4]。共有

種。

用python語(yǔ)言描述就是：

def getSubLists(lis=[],m=0):

allAns=[]

# type your code here

return allAns

| 輸入： [1，2，3，4]

| 輸出：[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

問(wèn)題分析：

從數(shù)學(xué)角度來(lái)看，從n個(gè)數(shù)字中任取m個(gè)，所有可能的取法總數(shù)量為：

。用Python求這個(gè)數(shù)量結(jié)果是很簡(jiǎn)單的，但是要實(shí)際輸出所有組合時(shí)，卻不是易事(對(duì)我自己而言)。

就我自己的經(jīng)驗(yàn)而言，例如從[a,b,c,d,e]中任選3個(gè)，我一般會(huì)采用如下搜索方式手動(dòng)去找出所有組合：

這種方法反映了一種遞歸思想：

選定了原列表種第

個(gè)數(shù)作為子列表第一個(gè)數(shù)，接下來(lái)就是把原列表第

數(shù)作為子列表第二個(gè)數(shù)，最后從原列表第

個(gè)數(shù)后面的所有數(shù)中任選一個(gè)作為子列表第三個(gè)數(shù)。

也就是說(shuō)，一旦確定了“誰(shuí)”作為子列表第一個(gè)數(shù)，那么接下來(lái)采用的方法都是一樣的，這不就是遞歸嘛!

編程實(shí)現(xiàn)：

若要采用遞歸方式，那問(wèn)題描述中的函數(shù)getSubLists不能直接調(diào)用自己，因?yàn)槊看巫晕艺{(diào)用后，存儲(chǔ)結(jié)果的allAns會(huì)被刷新，所以可以定義輔助函數(shù)subLists專門(mén)用來(lái)做遞歸：

def getSubLists(lis=[],m=0):

allAns = [] #用來(lái)存儲(chǔ)所有遞歸中的子列表

ans = [None for i in range(m)] #預(yù)先填充m個(gè)None,用來(lái)存儲(chǔ)每次遞歸中的子列表

subLists(lis,m,ans,allAns)

return allAns

def subLists(lis=[],m=0,ans=[],allAns=[]):

# recursive function codes

if m==0:

# m==0是某次遞歸返回的條件之一：子列表的第三個(gè)數(shù)已經(jīng)選出。

# 意味著已到達(dá)某個(gè)方向的最大遞歸深度

print('allAns is ',allAns,'before append ans:',ans)

allAns.append(ans.copy())

#這里有意思了，如果不用copy,那么ans即使已經(jīng)存儲(chǔ)在allAns，也會(huì)被其它遞歸方向中的ans刷新

print('allAns is ', allAns, 'after append ans:', ans)

return

if len(lis)

# 遞歸函數(shù)直接返回的條件之一：從4個(gè)數(shù)里面選5個(gè)數(shù)出來(lái)是不可能的。

print("short list!")

return

length=len(lis)

for iter in range(length-m+1): #可以作為子列表一員的數(shù)在lis中的index

ans[-m]=lis[iter] #lis[iter]作為子列表倒數(shù)第m個(gè)數(shù)

if iter+1

subLists(lis[iter+1:],m-1,ans,allAns)

else:

print('allAns is ', allAns, 'before append ans:', ans)

allAns.append(ans.copy())

print('allAns is ', allAns, 'after append ans:', ans)

return

好了，是不是挺簡(jiǎn)單的，來(lái)試一下效果：

if __name__=='__main__':

liss=[1,2,3,4]

m=3

print('The answer for choosing any 3 Numbers from the list:',getSubLists(liss,m))

Outputs:

allAns is [] before append ans: [1, 2, 3]

allAns is [[1, 2, 3]] after append ans: [1, 2, 3]

allAns is [[1, 2, 3]] before append ans: [1, 2, 4]

allAns is [[1, 2, 3], [1, 2, 4]] after append ans: [1, 2, 4]

allAns is [[1, 2, 3], [1, 2, 4]] before append ans: [1, 3, 4]

allAns is [[1, 2, 3], [1, 2, 4], [1, 3, 4]] after append ans: [1, 3, 4]

allAns is [[1, 2, 3], [1, 2, 4], [1, 3, 4]] before append ans: [2, 3, 4]

allAns is [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]] after append ans: [2, 3, 4]

The answer for choosing any 3 Numbers from the list: [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

Bingo! 歡迎指教

總結(jié)

以上是生活随笔為你收集整理的python递归排序组合_如何用Python求list的排列组合：一种递归方式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。