[Tutor] Creating lists with definite (n) items without repetitions
Francesco Loffredo
fal at libero.it
Wed Sep 9 19:45:43 CEST 2015
On 09/09/2015 18:59, Oscar Benjamin wrote:
> On 9 September 2015 at 12:05, Francesco Loffredo via Tutor
> <tutor at python.org> wrote:
>> 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
>
That's very interesting! This takes me to my question to Tutors:
what's wrong with the above code?
Francesco
More information about the Tutor
mailing list