时间戳

首页 > 解决方案 > 在更大的列表中选择随机的不同和不相交的列表

python - 在更大的列表中选择随机的不同和不相交的列表

问题描述

我正在使用 Sage 9.1（或 Python 3）进行编码。

我有一个相当大的列表big_list，其中的每个元素big_list本身就是一个恒定的小长度列表t。例如t=8，在 中大约有 40.000 个列表big_list。

我想随机选择 in big_list,n列表 (n是固定的, between 1and t-1), 这样n元素都是不同的并且都是成对不相交的：例如如果 [a,c] 和 [a,d] 是big_list我无法选择的两个元素一起。我知道这样的选择总是存在的，因为我有一些限制，t并且n

到目前为止我所做的方式：我首先在 中选择一个随机列表random_list，big_list然后使用列表推导创建一个big_list仅包含不相交元素的新列表random_list。通过空列表的隐式布尔值检查交集。但是，我的这部分代码在运行时方面是迄今为止最慢的（它被多次使用），任何改进都会很棒。

这是一个最小的工作示例。任何帮助表示赞赏，谢谢。

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

标签： pythonlistrandomsage

解决方案

这里有一些想法，不确定每个想法会带来什么加速。

判断交叉点是否为空不需要计算交叉点。

所以intersection可以去，主循环可以变成：

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

可以big_list就地修改，删除任何不与以下内容不相交的列表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))

最后，如果所有列表big_list都已排序，则可能会有更快的成员资格和不相交性检查。

推荐阅读