On 9 September 2015 at 12:05, Francesco Loffredo via Tutor
<tutor@python.org> wrote:
> 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)
I don't think the code above works. For n=27 it should count 117
(according to the formula I showed) but instead it comes up with 101.
I tried it with a smaller n by setting pool to range(1, 9+1) meaning
that n=9. The output is:
combos contains 84 triples.
maketriples(combos) contains 8 triples.
[(1, 2, 3),
(1, 4, 5),
(1, 6, 7),
(1, 8, 9),
(2, 4, 6),
(2, 5, 7),
(3, 4, 7),
(3, 5, 6)]
However I can construct a set of 12 triples containing each number
exactly 4 times which is the exact Steiner triple system:
1 6 8
1 2 3
1 5 9
1 4 7
2 6 7
2 4 9
2 5 8
3 5 7
3 6 9
3 8 4
4 5 6
7 8 9
This is the number of triples predicted by the formula: 9*(9-1)/6 = 12
--
Oscar
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
