I have a model that simulates a community of 8 agents in pairs. I want to create a list of 7 consecutive lists in such a way that all agents are paired with all agents. Something like this, for example:
[[(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)]]
I've created a function that generates the 7 lists, but I still need to incorporate no repetition to ensure that each agent is paired with each agent only once.
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))
The first thing that occurred to me was to keep in a set all the pairs that were formed in each "gene", and reject the "gene" that had intersections with that set. In this way a new "gene" is only added to the list
pairs
if it does not intersect with the set of previously generated pairs.In order for the pair
(3,2)
to be considered equal to(2,3)
, it is sorted before entering it into the set of pairs already seen, and thus both are converted to the "same" element(2,3)
.This function implements that idea:
Example of output produced:
Although the method produces correct results, in practice it is quite inefficient since, as cases are added to the result, it is increasingly difficult to find new cases that do not have intersections with the pairs already generated. By slightly modifying the above code you can count how many "failed attempts" you have to make before finding 7 that work. I get about 300 failed attempts to get 7 successful.
However, that shouldn't take too long, and although it finishes in two hundredths of a second on my computer, for some unknown reason the same code executed in Collaboratory never finishes (I've left it for several minutes).
Another alternative
This alternative may be more inefficient, but at least it has a deterministic execution time, since it does not depend on random collisions.
It is a matter of generating all the possible "genes" in advance, and then taking 7 of them at random.
I generate these "gen" by using all the permutations of the agents (with
itertools.permutations
), and then converting each permutation into an ordered tuple of ordered tuples. Thus, two apparently different permutations such as12345678
and78124365
, once each pair is ordered and these within the gene, both give rise to the same tuple:((1,2), (3,4), (5,6), (7,8))
. I put these tuples into a set and in this way I make sure that each one that is "unique" appears only once.Finally I convert the resulting set to a list, to make it a
shuffle()
and take 7 elements.This is the code:
On my machine this one takes considerably longer than the first one (about three tenths of a second, which isn't much, but it's an order of magnitude). But in Colaboratory it also ends quickly. The execution time is more deterministic.
And the advantage is that it scales much better if instead of 7 rows we want, for example, 20. Since we already have all the cases pre-generated (and I have counted that they are 105), it is the same for us to extract 7 than 70. In the first algorithm on the other hand, the more rows we want, the longer it will take because more collisions will occur as we generate cases.