[Tutor] Creating lists with definite (n) items without repetitions
Francesco Loffredo
fal at libero.it
Wed Sep 9 13:05:52 CEST 2015
Oscar Benjamin wrote:
The problem is that there are 26 people and they are divided into
groups of 3 each day. We would like to know if it is possible to
arrange it so that each player plays each other player exactly once
over some period of days.
It is not exactly possible to do this with 26 people in groups of 3.
Think about it from the perspective of 1 person. They must play
against all 25 other people in pairs with neither of the other people
repeated: the set of pairs they play against must partition the set of
other players. Clearly it can only work if the number of other players
is even.
I'm not sure but I think that maybe for an exact solution you need to
have n=1(mod6) or n=3(mod6) which gives:
n = 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...
The formula for the number of triples if the exact solution exists is
n*(n-1)/6 which comes out as 26*25/6 = 108.33333 (the formula doesn't
give an integer because the exact solution doesn't exist).
------------------------------------
A quick solution is to add one "dummy" letter to the pool of the OP's
golfers.
I used "!" as the dummy one. This way, you end up with 101 triples, 11
of which contain the dummy player.
But this is better than the 25-item pool, that resulted in an incomplete
set of triples (for example, A would never play with Z)
So, in your real-world problem, you will have 11 groups of 2 people
instead of 3. Is this a problem?
import pprint, itertools
pool = "abcdefghijklmnopqrstuvwxyz!"
def maketriples(tuplelist):
final = []
used = set()
for a, b, c in tuplelist:
if ( ((a,b) in used) or ((b,c) in used) or ((a,c) in used) or
((b,a) in used) or ((c,b) in used) or ((c,a) in used) ):
continue
else:
final.append((a, b, c))
used.add((a,b))
used.add((a,c))
used.add((b,c))
used.add((b,a))
used.add((c,a))
used.add((c,b))
return final
combos = list(itertools.combinations(pool, 3))
print("combos contains %s triples." % len(combos))
triples = maketriples(combos)
print("maketriples(combos) contains %s triples." % len(triples))
pprint.pprint(triples)
More information about the Tutor
mailing list