5

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!

5
  • Do you need every single pair or would 99% of them be enough? Sep 26, 2020 at 13:58
  • Can you provide some info about the strings themselves? Are all of them in the format 'abc' (3 letters)? Can they have similar letters like 'aab', or they are always different? Also can a list have similar strings? (eg 'xyz' 2 times, etc)
    – IoaTzimas
    Sep 26, 2020 at 14:05
  • You can use the slow solution to estimate the number of pairs by sampling 1/1000th of each list, running the slow algorithm, and multiplying by 1 million. There may just be way too many pairs. Sep 26, 2020 at 14:53
  • 99% of them would indeed be enough, and for more info about the strings, they are alphabetically sorted with anywhere between 1 and 26 letters, each letter of the alphabet can only appear once. Strings are also unique over both lists. Sep 26, 2020 at 23:42
  • Great suggestion David, unfortunately I am doubtful that I will find any solutions so the sampling method may miss the 1 in a million million solution Sep 26, 2020 at 23:43

4 Answers 4

7

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"])))
1
  • Incredible! This solution worked through my lists (both containing about 2 million strings respectively) in a mere 9.5 minutes on the dot! Thank you so much for your help :D Great idea to build an index for that efficient hashing check Sep 27, 2020 at 5:34
1

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')]
1
  • 3
    You're still looping over trillions of pairs, not sure why this would be appreciably better. Sep 26, 2020 at 14:00
1

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"])))
4
  • I had the same idea but failed to implement it, I'll give it a go. Thank you for your time! Sep 26, 2020 at 23:46
  • Receiving similar results from my attempts, it appears that (presumably) the overhead in this algorithm actually results in a running time about 100x slower than the brute force method (by very rough approximation, i.e. plus or minus a magnitude of 10) Sep 26, 2020 at 23:54
  • I wonder if there's a way to get this method as efficient as the other. It's so elegant. (Not that the other one isn't.) Sep 27, 2020 at 21:00
  • @גלעדברקן The optimization grouping words with the same set of letters carries over. I think to close the rest of the gap, we might switch to a static pivot order, to save the cost of repartitioning. Then in essence we can build a crit-bit tree and then traverse that using a similar algorithm to this one. Sep 27, 2020 at 22:12
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.