在Python中循环遍历循环？

Question

在Python中循环遍历循环？

8

我正在尝试解决Coderbyte的简单部分中的问题，提示如下：

函数ArrayAdditionI(arr)接受存储在arr中的数字数组，并返回字符串true，如果数组中的任何数字组合可以相加得到最大数字，则返回true，否则返回false。例如：如果arr包含[4, 6, 23, 10, 1, 3]，则输出应返回true，因为4 + 6 + 10 + 3 = 23。该数组不会为空，不会包含完全相同的元素，并且可能包含负数。

这是我的解决方案。

def ArrayAddition(arr):
arr = sorted(arr, reverse=True)
large = arr.pop(0)
storage = 0
placeholder = 0
for r in range(len(arr)):
    for n in arr:
        if n + storage == large: return True
        elif n + storage < large: storage += n
        else: continue
    storage = 0
    if placeholder == 0: placeholder = arr.pop(0)
    else: arr.append(placeholder); placeholder = arr.pop(0)
return False

打印ArrayAddition([2,95,96,97,98,99,100])

我甚至不确定这是否正确，但似乎覆盖了我输入的所有数字。我想知道是否有更好的算法来解决这个问题，但我对算法一无所知。我认为通过一个for循环内嵌另一个for循环等等的方式可以解决问题，但我不知道如何做到这一点。

我的想法是通过A+B，A+C，A+D ... A+B+C ... A+B+C+D+E来完成这个任务。

例如)

for i in range(len(arr):
print "III: III{}III".format(i)
storage = []
for j in range(len(arr):
    print "JJ: II({}),JJ({})".format(i,j)

    for k in range(len(arr):
        print "K: I{}, J{}, K{}".format(i,j,k)

我已经搜索了很多，发现了itertool的建议，但是我想知道是否有一种更原始的方法来编写这个代码。

谢谢。

- user3015876

在谷歌上搜索“子集和问题”，这应该能帮助你入门。 - thefourtheye

顺便提一下，你所称之为数组的并不是真正的数组。它们是列表（确切地说是ArrayLists，但无论如何都是列表）。在Python中，“数组”通常指的是NumPy数组，这是一种不同的数据结构。 - Max Noel

6个回答

2

你的解决方案不起作用。

>>> ArrayAddition([10, 11, 20, 21, 30, 31, 60])
False

简单的解决方案是使用 itertools 来迭代输入中不包含最大数的所有子集：

def subsetsum(l):
    l = list(l)
    target = max(l)
    l.remove(l)
    for subset_size in xrange(1+len(l)):
        for subset in itertools.combinations(l, subset_size):
            if sum(subset) == target:
                return True
    return False

如果你想避免使用itertools，你需要直接生成子集。这可以通过二进制计数并使用设置的位来确定要选择哪些元素来实现：

def subsetsum(l):
    l = list(l)
    target = max(l)
    l.remove(l)
    for subset_index in xrange(2**len(l)):
        subtotal = 0
        for i, num in enumerate(l):
            # If bit i is set in subset_index
            if subset_index & (1 << i):
                subtotal += num
        if subtotal == target:
            return True
    return False

- user2357112

啥？你什么意思？ - aIKid

0

更新：我忘记了你想要检查所有可能的组合。请改用以下方法：

def ArrayAddition(l):
    for length in range(2, len(l)):
        for lst in itertools.combinations(l, length):
            if sum(lst) in l:
                print(lst, sum(lst))
                return True
    return False

一行代码解决方案：

>>> any(any(sum(lst) in l for lst in itertools.combinations(l, length)) for length in range(2, len(l)))

希望这有帮助！

- aIKid

0

生成幂集的所有和并将它们与最大值进行测试

def ArrayAddition(L):
    return any(sum(k for j,k in enumerate(L) if 1<<j&i)==max(L) for i in range(1<<len(L)))

你可以通过进行一些预处理来改进这个 - 首先找到最大值，然后从L中删除它

- John La Rooy

0

另一种方法是...

代码：

import itertools
def func(l):
    m = max(l)
    rem = [itertools.combinations([x for x in l if not x == m],i) for i in range(2,len(l)-1)]
    print [item for i in rem for item in i if sum(item)==m ]


if __name__=='__main__':
    func([1,2,3,4,5])

输出：

[(1, 4), (2, 3)]

希望这能有所帮助.. :)

- Sravan K Ghantasala

0

如果我理解问题正确的话，这个简单的代码应该可以返回你想要的结果：

2*max(a)<=sum(a)

- VIKASH JAISWAL

抱歉，我认为您没有正确理解问题 :) - thefourtheye

嗯，这正是我所怀疑的 :) - VIKASH JAISWAL

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- perreal · Accepted Answer

一种递归解决方案：

def GetSum(n, arr):
    if len(arr) == 0 and n != 0:
        return False
    return (n == 0 or  
      GetSum(n, arr[1:]) or  
      GetSum(n-arr[0], arr[1:]))

def ArrayAddition(arr):
    arrs = sorted(arr)
    return GetSum(arrs[-1], arrs[:-1])

print ArrayAddition([2,95,96,97,98,99,100])

GetSum 函数在需要的总和非零且数组中没有项目时返回 False。然后它会检查以下三种情况：

如果所需总和 n 为零，则目标已实现。
如果我们可以在去除第一个项目后使用剩余项达到总和，则目标已实现。
如果我们可以在列表的其余部分上减去列表的第一个元素以得到所需总和，则目标已实现。