查找两个列表之间的相似之处 [英] Find similarities between two lists

问题描述

我有两个数字列表(L1 和 L2).我必须找出 L1 的任何组合是否在 L2 数字的任何组合中.

I have two lists of numbers (L1 and L2). And I have to find whether any combination of L1 is in any combination of L2 numbers.

我尝试通过 powerset() 函数进行双循环.不过是慢慢的.

I have tried a double loop through a powerset() function. However it is slowly.

powerset() 生成器:technomancy.org/python/powerset-generator-python.

powerset() generator: technomancy.org/python/powerset-generator-python.

我不会发布代码，因为我需要的是一些想法、方法或任何可以启发我的东西.

I don't post the code as what I need is some ideas, approaches or whatever could iluminate me.

额外问题:就数字的长度和范围而言，ListA 可能是一个怪物列表

Extra problem: ListA could be a monster list in terms of length and range of the numbers

推荐答案

这里是动态编程方法.如果你有整数，它会工作得很好.这里的胜利是你只跟踪一种方法来获得任何特定的总和，这意味着你的表现受到总和数量的限制.

Here is the dynamic programming approach. If you have integers it will work well. The win here is that you only track one way to get to any particular sum, which means that your performance is bounded by the number of sums.

def all_sums (numbers):
    answer = {0: None}
    for n in numbers:
        next_answer = {}
        for s, path in answer.iteritems():
            next_answer[s] = path
            next_answer[round(s + n, 8)] = [n, path]
        answer = next_answer
    if answer[0] is None:
        answer.pop(0)
    return answer

def find_matching_sum (numbers1, numbers2):
    sums1 = all_sums(numbers1)
    sums2 = all_sums(numbers2)
    for s1, path1 in sums1.iteritems():
        if s1 in sums2:
            return [s1, path1, sums2[s1]]
    return None

listA = [455, 698, 756, 3.56, -9]

listB = [526,55,943,156,531,304,618,911,598,498,268,926,899,898,131,966,303,936,509,67,976,639,74,935,23,226,422,280,64,975,583,596,583]
print(find_matching_sum(listA, listB))

对于浮点数，我建议尝试乘以一个公分母来得到整数.这是为了处理 0.1 + 0.2 != 0.3 问题.另请注意，使用浮点数很容易获得非常非常多的可能和，因此动态编程方法不再是一种胜利.举一个极端的例子，考虑 [..., 8, 4, 2, 1, 0.5, 0.25, 0.125, ...] 现在整个 powerset 都出来玩了...

With floating point, I would suggest trying to multiply by a common denominator to get to integers. This is to deal with the 0.1 + 0.2 != 0.3 problem. Also be aware that with floating point it is easy to have a very, very large number of possible sums, and so the dynamic programming approach is no longer a win. For an extreme example consider [..., 8, 4, 2, 1, 0.5, 0.25, 0.125, ...] and now the whole powerset comes out to play...

这篇关于查找两个列表之间的相似之处的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！