[Tutor] Creating lists with definite (n) items without repetitions

[Oscar Benjamin]

On 9 September 2015 at 12:05, Francesco Loffredo via Tutor
<tutor at 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