在两个列表中查找不包含公共字符的所有字符串对

Question

我有两个字符串列表，希望找到它们之间不包含公共字符的所有字符串对。例如

list1 = ['abc', 'cde']
list2 = ['aij', 'xyz', 'abc']

desired output = [('abc', 'xyz'), ('cde', 'aij'), ('cde', 'xyz')]

我需要它尽可能高效，因为我正在处理包含数百万个字符串的列表。目前，我的代码遵循以下一般模式：

output = []

for str1 in list1:    
    for str2 in list2:
        if len(set(str1) & set(str2)) == 0: 
             output.append((str1, str2))

这是 O(n^2) 并且需要很多小时才能完成运行，有人对如何加快速度有什么建议吗？也许有一种方法可以利用每个正在排序的字符串中的字符？

非常感谢您！

Answer 1

试试这个，如果有任何改进请告诉我：

import itertools

[i for i in itertools.product(list1, list2) if len(i[0]+i[1])==len(set(i[0]+i[1]))]

输出：

[('abc', 'xyz'), ('cde', 'aij'), ('cde', 'xyz')]

Answer 2

分析这个算法的运行时间很棘手，但这是我首先尝试的。这个想法是，给定一个字母，我们可以将问题分成三个子问题：（没有字母的单词，没有字母的单词），（没有字母的单词，有字母的单词），（有字母的单词，没有字母的单词信）。下面的代码选择这个字母（“枢轴”）来最大化消除的对数。在基本情况下，没有对可以被消除，我们只输出所有对。

Python 3，针对运行时间的可读性进行了优化。

import collections


def frequencies(words):
    return collections.Counter(letter for word in words for letter in set(word))


def partition(pivot, words):
    return (
        [word for word in words if pivot not in word],
        [word for word in words if pivot in word],
    )


def disjoint_pairs(words1, words2):
    freq1 = frequencies(words1)
    freq2 = frequencies(words2)
    pivots = set(freq1.keys()) & set(freq2.keys())
    if pivots:
        pivot = max(pivots, key=lambda letter: freq1[letter] * freq2[letter])
        no1, yes1 = partition(pivot, words1)
        no2, yes2 = partition(pivot, words2)
        yield from disjoint_pairs(no1, no2)
        yield from disjoint_pairs(no1, yes2)
        yield from disjoint_pairs(yes1, no2)
    else:
        for word1 in words1:
            for word2 in words2:
                yield (word1, word2)


print(list(disjoint_pairs(["abc", "cde"], ["aij", "xyz", "abc"])))

Answer 3

您可以对生成器使用递归：

from functools import reduce
list1 = ['abc', 'cde']
list2 = ['aij', 'xyz', 'abc']
def pairs(d, c = []):
   if not d and not reduce(lambda x, y:set(x)&set(y), c):
      yield tuple(c)
   elif d:
      yield from [i for k in d[0] for i in pairs(d[1:], c+[k])]

print(list(pairs([list1, list2])))

输出：

[('abc', 'xyz'), ('cde', 'aij'), ('cde', 'xyz')]

此答案使用 functools.reduce 来处理输入列表数量大于两个的情况。这样，可以更容易地计算潜在子列表中所有元素的集合交集。

Answer 4

这是另一个技巧，着重于将集合操作降低为位旋转和组合表示同一组字母的单词：

import collections
import string


def build_index(words):
    index = collections.defaultdict(list)
    for word in words:
        chi = sum(1 << string.ascii_lowercase.index(letter) for letter in set(word))
        index[chi].append(word)
    return index


def disjoint_pairs(words1, words2):
    index1 = build_index(words1)
    index2 = build_index(words2)
    for chi1, words1 in index1.items():
        for chi2, words2 in index2.items():
            if chi1 & chi2:
                continue
            for word1 in words1:
                for word2 in words2:
                    yield word1, word2


print(list(disjoint_pairs(["abc", "cde"], ["aij", "xyz", "abc"])))

在两个列表中查找不包含公共字符的所有字符串对

Find all pairs of strings in two lists that contain no common characters

python

string

algorithm

comparison