这个问题其实已经困扰我好久了, 也在网上看了非常多的教程, 始终都掌握不好. 有些代码很简洁, 但阅读性不强. 有些代码很长, 看着看着就走神了.

直到最近在弄DFS, 某天突然灵感一现, 觉得排列组合的问题可以用DFS的方法求解, 于是打开电脑, 顺着思路一点一点把代码敲下来, 没想到还真的可以.

觉得有必要把自己的思路记录下来, 万一将来忘了, 回头也能看看.

或者将来有了更好的思路, 也能回过头来对比一下.

 

全排列:

 

比如从[1,2,3,4,5]中, 选取5个数做全排列.

首先肯定是找第一位, 第一位一共有5种情况. 然后是第二位, 可选择的是4种, 以此类推, 可选择的数从第一位到第五位是[5,4,3,2,1].

比如我现在选的第1位是1, 那么第二位可选的就是[2,3,4,5], 如果第二位选择的是2, 那剩下的第三位可选的就是[3,4,5]

如果第一位我选的是2, 那第二位可选的就变成了[1,3,4,5]….

由上可知, 下一位可选的, 就是当前的array, 除去当前选择的那一位.

如果现在选择的是arr[i], 那么剩下的就是arr[:i] + arr[i+1:], 然后在剩下的这个array, 继续做全排列就好了. (比如, 在第一步循环到2的时候, 需要把第一位是1的情况再加回来, 因为[1,2] 和 [2,1] 是不同的排列 )

实现代码如下 (图片, wordpress好像对Code支持不太友好):

 

 

文字代码 –

def perm(curr, N, rest): #N,代表排列的位数, 要是全排列, 可以直接输入len(curr)

if
len(curr) == N: #已经满足所要的长度了, 就可以返回, 或者打印

print(curr)

else:

for j in
range(len(rest)):

t = curr + [rest[j]]

perm(t, N , rest[:j] + rest[j+1:])

#测试用例

arr = [1,2,3,4]

N = 4

i = 0

while i < len(arr):

perm([arr[i]],N, arr[:i] + arr[i+1:] )

i+=1

 

组合

 

弄懂了全排列, 组合问题就容易很多了.

比如要从[1,2,3,4,5]中选择3个做组合, 那我第一个可以选择的是[1,2,3,4,5]中的一个, 比如是2, 那下一位可以选择的是[1,3,4,5]中的一个. 每一次都会少一个. 直到选择到了规定的长度为止.

排列和组合唯一的区别是只需要往后走. 如果现在选择的是arr[i], 那么下一步的array就是arr[i+1:], 然后在
剩下的这个array里面再找, 这是因为[1,2,3], 和[2,1,3]是同样的组合.所以没有必要把先前的array[:i] 再加回来. (在第一步循环到2的时候, 后一位不会是1, 因为在处理1的时候, 已经把2处理过了)

代码如下 –

 

文字代码 –

def combo(curr, N, rest):

if
len(curr) == N: #已经满足所要的长度了, 就可以返回, 或者打印

print(curr)

else:

j = 0

while j < len(rest):

x = curr + [rest[j]] #把当前的数加到当前的array.

combo(x, N, rest[j+1:]) #每次只要往后再找就可以了

j+=1

#测试用例

arr = [1,2,3,4]

i = 0

while i < len(arr):

combo([arr[i]], 3, arr[i+1:])

i+=1