人生苦短,快学Python!
昨日遇到这样一道题,原题是借此讲述递归的思想,用 java 实现。
给定 4 种面额的钞票和目标金额,找出有多少种钞票组合,满足总金额等于目标金额。例如 [1, 2, 5, 10] 这4种面额,组合成 10元,那就有 10 张 1 元 / 8 张 1 元 + 1 张 2 元 ... / 1 张 10 元等情况。
笔者学习后打算用 python
复刻一波,于是有了以下的试验路径。
让我们先想想现实中用数钱的方式是怎么解决的,假如先从最小面额的组合开始考虑,那么我们先拿出 1 元,距离目标金额还差9元,接着再拿出 1 元,直至拿到 10 张 1 元,距离目标金额还差 0 元。如此便得到了第一种解法。
那么从更大面额的开始拿, 先拿出 2 元,距离目标金额还差得多,我们还可以继续拿小面额的,那就再拿 1 元,直至拿够10元,第二种解法就是 1 张 2 元 + 8 张 1 元。
第二种解法中是第一次拿出 2 元,那假如第一次拿 1 元,第二次再拿 2 元呢?基于排列组合,不同的数钱顺序也算作不同的解法,那解法可就太多了,下面就来看看在程序中如何利用递归实现吧!
先来看一下代码,传入目标金额,和一个空的钱包。从不同的面额中拿钱,把距离目标的差值作为下一层的目标金额,以及一个拿了一次钱的钱包。直到最终与目标金额差值为 0,返回一个装好钱的钱包,这个钱包中的钱是有放置顺序的。因为每种解法要换一个新的空包,所以需要进行深拷贝。
from copy import deepcopy
money_type = [1, 2, 5, 10]
possibility = []
def find_group(total=10, grp=[]):
if total==0:
print(grp)
possibility.append(grp)
return
if total<0:
return
for i in money_type:
new_grp = deepcopy(grp)
new_grp.append(i)
find_group(total-i, new_grp)
如此运行后,最终有 129 种解法之多!笔者就纳闷了,不同顺序也要算不同解法吗,如果要算作一种怎么办?
那么,让我们来想想怎么对结果列表去重。如何判断 [1, 3, 2] 实际上是否等于 [3, 1, 2] 呢?只需要对两者排序后进行比较即可,即 [1, 2, 3] 等于 [1, 2, 3]。因此,暴力遍历,两两排序对比即可。然后将重复的第二个索引位记录下来,最后按索引位过滤原始列表,得到新的去重列表。
def get_uni_lst(all_lst):
del_index = []
for i in range(0, len(all_lst)-1):
for j in range(i+1, len(all_lst)):
if sorted(all_lst[i])==sorted(all_lst[j]):
del_index.append(j)
uni_lst = [all_lst[i] for i in range(len(all_lst)) if i not in del_index]
return uni_lst
于是我们便得到了以下 11 种答案,更符合我们对现实需求的认知。
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1,1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1,1, 2, 5], [1, 1, 2, 2, 2, 2], [1, 2, 2, 5], [2, 2, 2, 2, 2], [5, 5], [10]]
说道去重,可以想到集合中是没有重复元素的,那么我们还可以借助集合来进行高效去重(经过大佬小明哥的提示)。但首先,我们需要将待去重列表转换为内部有序的元组。
def get_uni_lst_set(all_lst):
new_tuples = []
for i in all_lst:
i.sort()
new_tuples.append(tuple(i))
return set(new_tuples)
通过集合,我们也得到了 11 种答案。
{(5, 5), (1, 1, 1, 2, 5), (1, 1, 1, 1, 1, 1, 1, 1, 1, 1), (1, 2, 2, 5), (10,), (2, 2, 2, 2, 2), (1, 1, 2, 2, 2, 2), (1, 1, 1, 1, 1, 5), (1, 1, 1, 1, 2, 2, 2), (1, 1, 1, 1, 1, 1, 1, 1, 2), (1,1, 1, 1, 1, 1, 2, 2)}
那么对于这个整个操作流程,有没有更优解呢?明佬提示了一个方案,利用 itertools 模块。其中的 combinations_with_replacement 方法可以帮我们列出可能的组合。先看看基本用法。
from itertools import combinations_with_replacement as comb
for i in comb([1, 2, 3], 3):
print(i)
输出在自身可重复、组合长度为 3 的情况下,对 [1, 2, 3] 的组合结果,有10种。
(1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 2) (1, 2, 3) (1, 3, 3) (2, 2, 2) (2, 2, 3) (2, 3, 3) (3, 3, 3)
那么就开始暴力遍历吧!把所有组合都列出来,记录求和为 10 的结果。
def find_grp_iter():
grp = []
for i in range(1, 11):
for j in comb([1, 2, 5, 10], i):
if sum(j) == 10:
grp.append(j)
return grp
答案也是 11 种。
[(10,), (5, 5), (1, 2, 2, 5), (1, 1, 1, 2, 5), (2, 2, 2, 2, 2), (1, 1, 1, 1, 1, 5), (1, 1, 2, 2, 2, 2), (1, 1, 1, 1, 2, 2, 2), (1, 1, 1, 1, 1, 1, 2, 2), (1, 1, 1, 1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 1, 1, 1, 1,1)]
最后验证一下各种方法的效率。可见在去重的表现上,集合霸主的地位不可动摇。而对于整个需求的实现,借助 itertools 模块自带的方法,可以通过更加简洁的代码来快速完成。
这里是 Seon塞翁,我们下篇再见。
人生苦短,快学Python