我有一个模型可以模拟由 8 个代理组成的社区。我想创建一个包含 7 个连续列表的列表,以使所有代理都与所有代理配对。像这样的东西,例如:
[[(1, 2), (3, 4), (5, 6), (7, 8)],
[(1, 3), (2, 4), (5, 7), (6, 8)],
[(1, 4), (2, 3), (5, 8), (6, 7)],
[(1, 5), (2, 6), (3, 7), (4, 8)],
[(1, 6), (3, 8), (5, 2), (7, 4)],
[(1, 7), (2, 8), (3, 5), (4, 6)],
[(1, 8), (3, 6), (5, 4), (7, 2)]]
我创建了一个生成 7 个列表的函数,但我仍然需要不重复以确保每个代理只与每个代理配对一次。
import random
agents = [1,2,3,4,5,6,7,8]
def group(agents):
pairs = []
for round in range(7):
random.shuffle(agents)
gen = zip(*[iter(agents)]*2)
pairs.append(gen)
return pairs
print (group(agents))
我想到的第一件事是将每个“基因”中形成的所有对保留在一个集合中,并拒绝与该集合有交集的“基因”。
pairs
以这种方式,一个新的“基因”只有在它不与先前生成的对集合相交时才被添加到列表中。为了使该对
(3,2)
被认为等于(2,3)
,在将其输入到已经看到的对集合之前对其进行排序,因此两者都被转换为“相同”元素(2,3)
。这个函数实现了这个想法:
产生的输出示例:
尽管该方法产生了正确的结果,但实际上它的效率很低,因为随着案例被添加到结果中,越来越难以找到与已经生成的对没有交集的新案例。通过稍微修改上面的代码,您可以计算在找到 7 个有效之前您必须进行多少“失败的尝试”。我得到了大约 300 次失败的尝试来获得 7 次成功。
然而,这不应该花费太长时间,虽然它在我的计算机上完成了百分之二秒,但由于某种未知的原因,在 Collaboratory 中执行的相同代码永远不会完成(我已经离开了几分钟)。
另一种选择
这种替代方案可能效率更低,但至少它具有确定的执行时间,因为它不依赖于随机冲突。
就是提前生成所有可能的“基因”,然后随机抽取其中的7个。
我通过使用代理的所有排列(带有
itertools.permutations
)来生成这些“gen”,然后将每个排列转换为有序元组的有序元组。因此,两个明显不同的排列,例如12345678
和78124365
,一旦每一对被排序并且这些在基因内,都产生相同的元组:((1,2), (3,4), (5,6), (7,8))
。我将这些元组放入一个集合中,以这种方式确保每个“唯一”的元组只出现一次。最后,我将结果集转换为列表,使其成为 a
shuffle()
并采用 7 个元素。这是代码:
在我的机器上,这个比第一个花费的时间要长得多(大约十分之三秒,虽然不多,但它是一个数量级)。但在 Colaboratory 中,它也很快结束。执行时间更具确定性。
优点是,如果我们想要的不是 7 行,例如 20 行,它的扩展性会更好。由于我们已经预先生成了所有案例(我已经算过它们是 105 个),所以对我们来说也是一样的提取 7 而不是 70。另一方面,在第一个算法中,我们想要的行越多,所需的时间就越长,因为在生成案例时会发生更多的冲突。