1

I am trying to write some efficient python code that will identify items that appear together on multiple lists. For example, in the dictionary of lists

list_of_lists = {'lista':list('abcdefhmqr'),
                 'listb':list('abdgklmr'),
                 'listc':list('abcdgjkmr'),
                 'listd':list('abcdglmrt'),
                 'liste':list('admoprst')}

'adrm' appear together on all five lists, while 'abdm','abdr','abmr', and 'bdmr' appear together on four lists, and many combinations of four letters appear on three lists or two.

Here is the code:

def make_dict(lists):
    # creates a dictionary with each unique item as the key,
    # and a set of lists the item appears on as the value
    letter_dict={}
    for item in lists.items():
        for letter in item[1]:
            if letter in letter_dict:
                letter_dict[letter].add(item[0])
            else:
                letter_dict[letter] = set([item[0]])
    return OrderedDict(sorted(letter_dict.items(),key=lambda x:x[0]))

def find_matches(dictionary):
    # takes a dictionary with tuples of list elements as keys
    # and lists they appear on as values, and finds the intersection with 
    # the master list of elements and their lists
    matches={}
    for key in dictionary.keys():
        index_of_key = index_of_attr_keys.index(key[-1])
        for next_key in islice(master_list,index_of_key+1,None):
            intersection = dictionary[key] & master_list[next_key]
            if len(intersection)>1:
                new_key = set(key)
                new_key.add(next_key[0])
                new_key = tuple(sorted(new_key))
                matches[new_key] = intersection
    return matches

master_list = make_dict(list_of_lists)
index_of_attr_keys = sorted(master_list.keys())

I can iteratively make dictionaries with keys of tuples with two, three, four, etc. items

doubles = find_matches(master_list)
triples = find_matches(doubles)
quads = find_matches(triples)

My code works on this toy example, but it is not particularly fast when I run it on my actual data set, which is over 84,000 unique elements appearing on hundreds of lists. Starting with my list of list of 84,000+ unique elements, it takes an hour to generate a list of 1.2 million pairs that appear together on more than one list, and things just get longer from there. I am wondering if there is a faster way to do this.

4
  • What is the expected output? Mar 29, 2020 at 22:40
  • Output would be a list of combinations of elements that I can sort to find the combinations that appear most frequently together.
    – rockman25
    Mar 29, 2020 at 22:55
  • So you want adrm, 'abdm','abdr','abmr', and 'bdmr' or just adrm ? What happens with ad that also appears 5 times? Mar 29, 2020 at 23:00
  • Some sample questions would be, Are there any 10 items that appear together on at least 20 lists? How many lists to the most-frequently co-occuring sets of 5 appear on? That sort of thing. I'm not looking for items that appear on every list. I know already that it's extremely unlikely that any do. But there are groups that definitely appear together.
    – rockman25
    Mar 29, 2020 at 23:38

2 Answers 2

2

Convert to set and take intersection between lists you want. e.g to find all elements which appear on all lists:

set.intersection(*[set(x) for x in list_of_lists.values()])

Output:

 {'a', 'd', 'm', 'r'}
2
  • Sorry, what does the * mean before the list? Is it just list unpacking of some sort?
    – OmO Walker
    Mar 29, 2020 at 22:54
  • List expansion. For example if you have def fn(a,b,c) you can call it as fn(1,2,3) or fn(*[1,2,3])
    – Arthur
    Mar 29, 2020 at 22:57
0

I'm going to rephrase your question slightly. My reading of this is that you seek the intersections of your sets of data, amongst the powerset on their keys.

The code below generates the powerset of your sets, running intersections on your data as it goes, bailing on that path when it hits a null intersection. The total number of leaves in your powerset is 2^n, so it's going to get gnarly if you have a huge number of sets with significant overlap. On the other hand, your intersections generally are pretty small, or get pretty small pretty fast, then only a tiny fraction of the full 2^n-wide tree will need to be visited.

You can also likely shrink the search space significantly by expressing the minimum set size you want and using that as the bail option on line 'if 0==len(intersection)', which may help a lot, but again that depends on your underlying data.

list_of_lists = {'lista':list('abcdefhmqr'),
                 'listb':list('abdgklmr'),
                 'listc':list('abcdgjkmr'),
                 'listd':list('abcdglmrt'),
                 'liste':list('admoprst'),
                 'listz':list('z'),
                 'listza':list('az')}

dict_of_sets = {k: set(v) for k, v in list_of_lists.items()}


def do_something_with_intersection(dict_of_sets, curr_keyset, curr_intersection):
    print("Intersection: " + str(curr_intersection) + " in sets: " + str(curr_keyset))

# Remaining_keys is the list of keys in dict_of_sets that are still unvisited
# dict_of_sets is all the underlying data
# curr_keyset is the current set of keys [drawn on dict_of_sets] - function visits the power set of those keys
# curr_intersection is the intersections of sets from dict_of_sets whose keys are in curr_set
def do_powerset_intersection(remaining_keys, dict_of_sets, curr_keyset=set(), curr_intersection=None):
    # Hit the end of the recursive adventure
    if 0 == len(remaining_keys):
        if 0 != len(curr_keyset):
            print("Found a Leaf: " + str(curr_keyset))
            do_something_with_intersection(dict_of_sets, curr_keyset, curr_intersection)
            print()
        return
    q = remaining_keys.pop()
    if curr_intersection is None:
        new_intersection = dict_of_sets[q]
    else:
        new_intersection = curr_intersection.intersection(dict_of_sets[q])

    if 0 == len(new_intersection):
        # Ran out of stuff to intersect - curr_intersection is best we can do on this path
        print("Didn't make it to a leaf, best we can do")
        do_something_with_intersection(dict_of_sets, curr_keyset, curr_intersection)
        print()
        return

    new_set = curr_keyset.copy()
    new_set.add(q)
    do_powerset_intersection(remaining_keys, dict_of_sets, curr_keyset, curr_intersection)
    do_powerset_intersection(remaining_keys, dict_of_sets, new_set, new_intersection)
    remaining_keys.append(q)


do_powerset_intersection(list(dict_of_sets.keys()), dict_of_sets)

Your Answer

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

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