代码之家 › 专栏 › 技术社区 › Mohamed Benkedadra

数组中每个元素的递归

dynamic-programming recursion list arrays python

Mohamed Benkedadra · 技术社区 · 7 年前

我有一个整数S和一组整数。我需要从集合中找到一组整数,其中这些整数的和等于S。它可以是1个整数或50-这无关紧要。

我试着这样做:

我有一个数组res和一个数组grp

res以[0]开头,grp是最初给定的集合,S是我们试图找到的和,S是全局的

my function takes(res,grp)

我想这样做:(和例子)

当res元素之和等于S时停止

但是我很讨厌递归,我不知道我应该做什么

这是我的密码

S = 7
grp = [0,5,6,4,3]

def sumFinder(res,grp):
    if grp == []:
        return grp #in case no pair was found [] is returned 
    if sum(res) == S:
        return res
    for i in range (0,len(grp)):
        print(res)
        print(grp[i])
        res += [grp[i]]
        newgrp = grp[:i]
        newgrp += grp[i+1:]
        return sumFinder(res,newgrp)

 print(sumFinder([0],grp))

更新:

谢谢大家的回答非常感谢。 英格利卢兹 感谢你给我一个更好的解决问题的想法,谢谢你,我得到了这个:

1-这是为了找到第一个组合并返回它(这是我的目标)

grp = [1,0,1,0,1,2,6,2,3,5,6,7,8,9,2,1,1,9,6,7,4,1,2,3,2,2]
S = 55
grps = []

def findCombination(comb,grp):
    for i in range (0,len(grp)):
        comb += [grp[i]]
        newgrp = grp[:i]
        newgrp += grp[i+1:]

        if sum(comb) == S:
            return comb

        if newgrp not in grps:
            grps.append(newgrp)
            res = findCombination([],newgrp)
            if res != None:
                return res

print(findCombination([],grp))

2-这是为了找到所有的组合:(这就是问题所在 英格利卢兹 谈到了,但我不太了解他的方法,尽管它看起来更好)

grp = [1,0,1,1,9,6,7,4,1,2,3,2,2]
S = 12
grps = []
combinations = []

def findAllCombinations(comb,grp):
    global combinations
    for i in range (0,len(grp)):
        comb += [grp[i]]
        newgrp = grp
        newgrp = grp[:i]
        newgrp += grp[i+1:]

        if sum(comb) == S and tuple(comb) not in combinations:
            combinations.append(tuple(comb))

        if newgrp not in grps:
            grps.append(newgrp)
            findAllCombinations([],newgrp)

findAllCombinations([],grp)
print(combinations)

我现在唯一的问题是,当S>50(在第一个中),找到答案需要更长的时间

你们能给我什么建议来改进这两种算法?

3 回复 | 直到 7 年前

englealuze 6 年前

我将向您展示如何思考这个问题以及如何在一般意义上解决这类问题,而不仅仅是提供代码。

首先,让我们重新表述你的问题。事实上,你想要的是对于给定的一组数字,找到满足特定条件的组合。因此,您可以将问题分解为两个不同的步骤。

查找集合的所有组合
筛选出满足特定条件的组合

让我们思考如何递归地解决第一个任务。请记住,如果一个问题可以用递归的方式解决,通常意味着数据中有一些递归模式,通常可以用非常简单明了的方式解决。如果最终得到的是一个混乱的递归解决方案,这几乎意味着你走错了方向。

让我们先看看数据的模式。如果你有一个很小的集合(1,2),那么这个集合中的组合是

1
2
1, 2

让我们在集合中增加一个成员,(1,2,3)。对于这个更大的集合,所有的战斗都是

1       | 1, 3
2       | 2, 3
1, 2    | 1, 2, 3
        | 3

让我们看看更大的集合(1、2、3、4)。可能的组合有

1       1, 3       | 1, 3, 4
2       2, 3       | 2, 3, 4
1, 2    1, 2, 3    | 1, 2, 3, 4
        3          | 3, 4
                   | 4

现在您看到了一些有趣的东西,一个较大集合的组合是较小集合加上附加到每个先前组合的附加元素和附加元素本身的组合。

假设您已经得到了具有一定大小的集合的所有组合的解,则可以从该解导出更大集合的解。这自然形成了一个递归。您可以将这种简单的英语直接翻译为递归代码,如下所示

# assume you have got all combinations of a smaller set -> combinations(smaller(L))
# the solution of your bigger set can be directly derived from it with known new element
def combinations(L):
    if L == []:
        return []
    else:
        return next_solution(combinations(smaller(L)), newitem(L))

请注意,我们是如何将解决较大问题的任务分解为解决较小问题的。您需要助手函数,如下所示

# in your case a smaller set is just the new set drop one element
def smaller(L):
    return L[1:]

# the new element would be the first element of new set
define newitem(L):
    return L[0]

# to derive the new solution from previous combinations, you need three parts
# 1. all the previous combinations -> L
# 2. new item appending to each previous combination -> [i + [newelement] for i in L]
# 3. the new item itself [[newelement]]
def next_solution(L, newelement):
    return L + [i + [newelement] for i in L] + [[newelement]]

现在我们知道了如何从集合中提取所有组合。然后要过滤它们,您不能将过滤器直接插入到递归步骤中,因为我们依赖之前的解决方案以递归方式构建结果列表。最简单的方法是过滤列表,同时获得所有组合的完整结果。

您将得到这样一个解决方案。

def smaller(L):
  return L[1:]

def newitem(L):
  return L[0]

def next_solution(L, newelement):
  return L + [i + [newelement] for i in L] + [[newelement]]

def filtersum(L, N, f=sum):
  return list(filter(lambda x: f(x)==N, L))

def combinations(L):
  if L == []:
    return []
  else:
    return next_solution(combinations(smaller(L)), newitem(L))

def filter_combinations(L, N, f=filtersum):
  return f(combinations(L), N)

print(filter_combinations([0,5,6,4,3], 7))
# -> [[3, 4], [3, 4, 0]]

通过在每次递归调用中过滤出总和大于定义值的组合,可以节省一些计算,例如

def combinations(L):
  if L == []:
    return []
  else:
    return next_solution(list(filter(lambda x: sum(x) <=5, combinations(smaller(L)))), newitem(L))

print(combinations([1,2,3,4]))
# -> [[4], [3], [3, 2], [2], [4, 1], [3, 1], [3, 2, 1], [2, 1], [1]]

事实上,递归有不同的方法,这取决于您如何将问题分解为更小的问题。有一些更聪明的方法,但我上面展示的方法是解决这类问题的典型和通用方法。

我有用这种方法解决其他问题的例子

Python: combinations of map tuples

Sphinx 7 年前

下面的代码起作用(删除循环中的“直接返回”,改为条件“返回”)。

但我认为这不是一个好的解决方案。您需要改进算法。

PS:此代码也将只返回一个匹配项,而不是所有匹配项。

S = 7
grp = [0,3,6,4,6]

result = []

def sumFinder(res,grp, result):
    for i in range (0,len(grp)):
        temp = list(res) #clone res instead of direct-reference
        if grp == [] or not temp:
            return grp #in case no pair was found [] is returned
        if sum(temp) == S:
            result.append(tuple(temp))
            return temp
        temp.append(grp[i])
        newgrp = grp[:i] + grp[i+1:]
        sumFinder(list(temp),newgrp, result)

sumFinder([0], grp, result)
print result

测试用例:

S = 7
grp = [0,3,6,4,6]
result = [(0, 0, 3, 4), (0, 0, 4, 3), (0, 3, 0, 4), (0, 3, 4), (0, 4, 0, 3), (0, 4, 3)]
[Finished in 0.823s]

Aaditya Ura 7 年前

你能告诉我你在哪里发现这个问题的吗?我喜欢解决这类问题,Bdw以下是我的方法:

a=[[[0],[0,5,6,4,3]]]

s=7

def recursive_approach(array_a):
    print(array_a)
    sub=[]
    for mm in array_a:
        array_1 = mm[0]
        array_2 = mm[1]
        if sum(array_2)==s:
            return "result is",array_2
        else:
            track = []
            for i in range(len(array_2)):
                c = array_2[:]
                del c[i]

                track.append([array_1 + [array_2[i]], c])
            sub.append(track)
    print(sub)
    return recursive_approach(sub[0])





print(recursive_approach(a))

输出:

[[[0], [0, 5, 6, 4, 3]]]
[[[[0, 0], [5, 6, 4, 3]], [[0, 5], [0, 6, 4, 3]], [[0, 6], [0, 5, 4, 3]], [[0, 4], [0, 5, 6, 3]], [[0, 3], [0, 5, 6, 4]]]]
[[[0, 0], [5, 6, 4, 3]], [[0, 5], [0, 6, 4, 3]], [[0, 6], [0, 5, 4, 3]], [[0, 4], [0, 5, 6, 3]], [[0, 3], [0, 5, 6, 4]]]
[[[[0, 0, 5], [6, 4, 3]], [[0, 0, 6], [5, 4, 3]], [[0, 0, 4], [5, 6, 3]], [[0, 0, 3], [5, 6, 4]]], [[[0, 5, 0], [6, 4, 3]], [[0, 5, 6], [0, 4, 3]], [[0, 5, 4], [0, 6, 3]], [[0, 5, 3], [0, 6, 4]]], [[[0, 6, 0], [5, 4, 3]], [[0, 6, 5], [0, 4, 3]], [[0, 6, 4], [0, 5, 3]], [[0, 6, 3], [0, 5, 4]]], [[[0, 4, 0], [5, 6, 3]], [[0, 4, 5], [0, 6, 3]], [[0, 4, 6], [0, 5, 3]], [[0, 4, 3], [0, 5, 6]]], [[[0, 3, 0], [5, 6, 4]], [[0, 3, 5], [0, 6, 4]], [[0, 3, 6], [0, 5, 4]], [[0, 3, 4], [0, 5, 6]]]]
[[[0, 0, 5], [6, 4, 3]], [[0, 0, 6], [5, 4, 3]], [[0, 0, 4], [5, 6, 3]], [[0, 0, 3], [5, 6, 4]]]
[[[[0, 0, 5, 6], [4, 3]], [[0, 0, 5, 4], [6, 3]], [[0, 0, 5, 3], [6, 4]]], [[[0, 0, 6, 5], [4, 3]], [[0, 0, 6, 4], [5, 3]], [[0, 0, 6, 3], [5, 4]]], [[[0, 0, 4, 5], [6, 3]], [[0, 0, 4, 6], [5, 3]], [[0, 0, 4, 3], [5, 6]]], [[[0, 0, 3, 5], [6, 4]], [[0, 0, 3, 6], [5, 4]], [[0, 0, 3, 4], [5, 6]]]]
[[[0, 0, 5, 6], [4, 3]], [[0, 0, 5, 4], [6, 3]], [[0, 0, 5, 3], [6, 4]]]
('result is', [4, 3])