这个问题其实已经困扰我好久了, 也在网上看了非常多的教程, 始终都掌握不好. 有些代码很简洁, 但阅读性不强. 有些代码很长, 看着看着就走神了.
直到最近在弄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