Selecting random distinct and disjoint lists in a larger list

Question

I'm coding in Sage 9.1 (Or Python 3).

I have a fairly large list big_list, each element of big_list is itself a list of constant small length t. For example for t=8, there are about 40.000 lists in big_list.

I want to randomly select in big_list, n lists (n is fixed, between 1 and t-1), such that the n elements are all distinct and all pairwise disjoint : For example if [a,c] and [a,d] are two element of big_list I cannot select them together. I know that such a selection always exist given some constraint I have on t and n

The way I do so far : I start by selecting one random list random_list in big_list, then using a list comprehension to create a new big_list containing only the elements not intersecting random_list. The intersection is checked by the implicit booleanness of the empty list. However this part of my code is by far the slowest in term of runtime (it is used many many times), any improvement would be great.

Here is a minimal working example. Any help is appreciated, thanks.

import random

def intersection(list1, list2):
    """Intersection of two lists"""
    temp = set(list2)
    list3 = [value for value in list1 if value in temp]
    return list3

t=4
n=2

output=list()

#example of big_list, here I could select elements 0 and 2, or elements 1 and 3
#note that for any first choice of random_list, it is always possible to select a second one.
big_list=[[1,2,3,4],[1,2,5,6],[5,6,7,8],[3,4,7,8]]

random_list = random.choice(big_list)
output.append(list(random_list))

#looping on the number of disjoint lists I need
for i in range(1,n):
    #using a list comprehension to create a new big_list containing only the elements not intersecting random_list
    #the intersection is checked by the implicit booleanness of the empty list
    big_list = [l for l in big_list if not intersection(l,random_list)]

    random_list = random.choice(big_list)
    output.append(list(random_list))
    
output

user_3827575 · Answer

Here are a few ideas, not sure what speedup each brings.

Deciding whether the intersection is empty does not require computing the intersection.

So intersection can go and the main loop can become:

# need n disjoint lists, already have 1
for i in range(1, n):
    # new big_list with only lists disjoint from random_list
    big_list = [l for l in big_list if not any(x in random_list for x in l)]
    random_list = random.choice(big_list)
    output.append(list(random_list))

One can modify big_list in place, deleting any list not disjoint from random_list:

# need n disjoint lists, already have 1
for i in range(1, n):
    # prune big_list of any list not disjoint from random_list
    k = 0
    while k < len(big_list):
        if any(x in random_list for x in big_list[k])
            del big_list[k]
        else:
            k += 1
    random_list = random.choice(big_list)
    output.append(list(random_list))

Finally, if all lists in big_list are sorted, there might be faster membership and disjointness checks.

Selecting random distinct and disjoint lists in a larger list

1 Answers