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

user_10742866 0
Viewed 383

I have two lists of strings, and wish to find all pairs of strings between them that contain no common characters. e.g.

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

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

I need this to be as efficient as possible because I am processing lists with millions of strings. At the moment, my code follows this general pattern:

output = []

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

This is O(n^2) and is taking many hours to run, does anyone have some suggestions for how to speed this up? Perhaps there is a way to take advantage of characters in each string being sorted?

Thank you very much in advance!

algorithm python comparison string
4 Answers

Here's another tack, focusing on lowering the set operations to bit twiddling and combining words that represent the same set of letters:

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"])))
user_21446690

Try this and tell me if there is any improvement:

import itertools

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

Output:

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

It's tricky to analyze the running time of this algorithm, but it's what I'd try first. The idea is that, given a letter, we can split the problem into three subproblems: (words without the letter, words without the letter), (words without the letter, words with the letter), (words with the letter, words without the letter). The code below chooses this letter (the "pivot") to maximize the number of pairs eliminated. In the base case, no pair can be eliminated, and we just output all pairs.

Python 3, optimized for readability over running time.

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"])))
user_21446690

You can use recursion with a generator:

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])))

Output:

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

This answer uses functools.reduce in order to handle cases where the number of input lists is greater than two. That way, the set intersection of all the elements in the potential sublist can more easily computed.

user_73267380
Related