Python复刻一道题，学到了~

人生苦短，快学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模块方法

那么对于这个整个操作流程，有没有更优解呢？明佬提示了一个方案，利用 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