如何从元组创建所有组合的总和？(采访)

Question

我在面试时遇到了一个问题,这很有挑战性.该主题基于决策分析.问题是让我们假设我们有一个元组;

(15, 8, 8, 3)

并且我们希望逐个创建所有组合的所有总和,而不重复和求和相同的数字,例如此输出;

[(23, 8, 3), (18, 8, 8), (15, 11, 8)]

另一个例子;

(6, 5, 3, 8)

输出是:

[(11, 3, 8), (9, 5, 8), (14, 5, 3), (6, 8, 8), (6, 13, 3), (6, 5, 11)]

注意:订单很灵活.

我真的很想知道答案,所以如果有人对这个编码挑战感兴趣,会帮助我改善思维结构.

Answer 1

我认为解决这类问题的最佳方法是从缓慢,强力的解决方案开始,因为这样您就可以直观地看到工作的进展情况.其他人不同意并且更愿意预先考虑可能的算法,但这是我的答案,所以...

首先忽略重复的数字规则,使事情更简单:

def sumcombos(tup):
    for i, x in enumerate(tup):
        for j, y in enumerate(tup[i+1:], i+1):
            yield tup[:i] + (x+y,) + tup[i+1:j] + tup[j+1:]

你应该能够理解它是如何工作的,对吧？

如果你明确需要list的tuples,而不是可迭代的,它包:

def sumcomboslist(lst):
    return list(sumcombos(lst))

现在,问题是这将输出(23, 8, 3)两次,并且它也将输出(15, 16, 3).避免这种情况的规则是"不重复和总结相同的数字".解释这意味着什么并不容易,^*但是一旦你这样做,实现它是:

def sumcombos(lst):
    for i, x in enumerate(lst):
        if x in lst[:i]: continue
        for j, y in enumerate(lst[i+1:], i+1):
            if y in lst[:j]: continue
            yield tup[:i] + (x+y,) + tup[i+1:j] + tup[j+1:]

那么,性能如何呢？好吧,内循环明显运行N**2时间,我们有一个if y in lst[:j]在该循环内需要线性时间的东西,所以它是N**3.现在,对于我们的例子,N有史以来最大的是4,这很好,但在大多数现实情况下,立方算法都是一个问题.

如果我们可以使用线性空间,我们可以通过构建一个前面的dict将每个值映射到它的第一个位置(只需要线性时间)来改进它,然后它if y in lst[:j]:变成恒定时间if first_positions[y] < j:.

然后我们可以进一步记忆这个memoization并缓存所有子列表的结果,因此内部循环只需要第一次计算每个子列表.

但是,一旦你完成了这个,你就可以看到实际发生了什么(如果不是,print在中间添加一些s)并想出更聪明的算法,它可以预先存储所有的总和.

_{*该规则含糊不清,本页面上的每个人(包括我)都猜错了.考虑到可以解释和查看预期输出的所有方式,我想我可以弄清楚它们必须具有什么意义.但在现实生活中,我绝对会要求他们澄清而不是猜测.对于一次采访来说更是如此,让你要求澄清可能实际上就是重点.}