主页 / 问题 / 590198
Accepted
Bernard
Asked:2020-11-13 00:24:31 +0000 UTC2020-11-13 00:24:31 +0000 UTC

比较两个列表以找到符合规则的元素

  • 772

问题是，例如我有两个列表：

lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']

如何在第二个列表中找到仅包含第一个列表中的那些元素的此类元素，但如果第一个列表中有一个单元，则例如第二个列表中的元素“112”不适合。

也就是说，程序的结果应该是

ls3 = ['123', '234']

'345' - 不匹配，因为有一个元素“5”不在第一个列表中

'334' - 不匹配，因为有两个“3”元素，而在第一个列表中只有一个“3”元素

python

5 个回答

  1. 这个问题可以通过使用标准的 multiset 类来解决Counter：

    from collections import Counter

lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']

base = Counter(lst1)
result = [s for s in lst2 if not (Counter(s) - base)]

    条件not (Counter(s) - base)检查s多重集中的元素不多于base

    • 10
  2. Best Answer

    如果知道如何确定是否有可能使用每个字符以不超过其重复次数（谓词已知）来组成word给定字符的字符串，那么问题就简化为：charschars can_build(word, chars)

    result = list(filter(can_build, lst2))

    或更具可读性：

    result = [word for word in lst2 if can_build(word)]

    can_build里面使用的地方chars = lst1。

    如果要求使用所有的字符chars，那么就是测试它是否是word一个变位词chars，例如：“enlightener”可以通过重新排列字母“patience”得到。当完全相等被“不再”取代时，您可以使用类似的解决方案。

    can_build()可以通过查找多重集是否是word 多重集的子集来实现chars。chars如果和中的所有字符word都是唯一的，则

    can_build = set("1234").issuperset

    collections.Counter实现了元素可以重复的集合的思想，即multiset。如@Timofey Bondarev的回答中的优雅解决方案所示，此集合可用于实现can_build：

    can_build = lambda word, chars=Counter(lst1): not (Counter(word) - chars)

    可以在不使用的情况下手动实现相同的算法collections.Counter。

    from collections import defaultdict

def Counter(letters):
    counts = defaultdict(int)
    for letter in letters:
        counts[letter] += 1
    return counts

chars_count = Counter(chars)

def can_build(word):
    return all(chars_count[char] >= count for char, count in Counter(word).items())

    如果所有字符都属于某个字母表，则可以使用简单列表，因为它chars始终相同，所以可以缓存chars.count这些值。例如，ifchars只能包含数字0-9：

    from string import digits

chars_count = [(digit, chars.count(digit)) for digit in digits]

def can_build(word):
    return all(word.count(digit) <= count for digit, count in chars_count)

    是O(N * M)解决方案（M=len(digits)-alphabet 大小），与O(N)使用Counter(). 如果字母表不固定：alphabet = set(word)，则它是一个O(N**2)（二次）算法。如果alphabet像示例中那样固定，那么这是一个O(N)（线性）解决方案。对于小字母表，例如布尔数字 ( alphabet=(0,1)) 或 DNA 字符串 ( alphabet="GTAC")，此解决方案甚至可能比使用 的解决方案更快Counter()。

    另一个应用示例：如果word，chars这些是由其质因数表示的数字（例如：(2,2,3)表示12，(5,7)表示35），则它can_build()回答是否是word除数的问题chars，即是否为真：chars % word == 0。

    问：如何实现代码，如果你摆脱了元素必须重复多次的条件，就像它在第一个列表中一样？？？

    这个假设中的答案已经有效。否则，字谜就是这种情况：重复次数相同。Counter()c和 c解决方案<=不>=要求元素重复“与第一个列表中的次数一样多”（尽可能少）。

    如果你的意思是重复次数根本不重要，而只对元素是否存在感兴趣，那么情况类似于所有元素都唯一的情况，即：

    can_build = set(lst1).issuperset

    正如上面已经提到的。

    • 7 
  3. [l2 for l2 in lst2 if all(l2.count(l) <= lst1.count(l) for l in set(l2))]
    • 5 
  4. #!/usr/bin/env python3.4
# -*- coding: utf-8 -*-
lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']
S1 = set(lst1)
S2 = set(lst2)
S3 = set()
for x in S2:
    if set(x) <= S1: S3.add(x)
lst3 = list(S3)
for x in lst3:
    for y in x:
        if x.count(y) > 1:
            count = lst3.index(x)
            continue
lst3.pop(count)
print(lst3)

    如果单纯按照事物的逻辑，没有什么特别的智慧。对集合（从学校学到的）、循环和列表有一点了解。回答 ['123', '234']

    • 2

  5. 上面的解决方案当然更短，但从人的角度来说，您可以这样做：

    список = ['1', '2', '3', '4']
список2 = ['123', '234', '345', '34']

результат = []
for сочетание in список2:
    временный_список = список[:]  # копия списка
    for цифра in сочетание:
        if цифра in временный_список:
            временный_список.remove(цифра)  # чтобы не более одной проверки на число
        else:
            break
    else: результат.append(сочетание)

print(результат)


===================== RESTART: C:\Python 3.5\задачка.py =====================
['123', '234', '34']
    • 0

相关问题