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

[Francesco Loffredo]

On 09/09/2015 19:45, Francesco Loffredo via Tutor wrote:
> On 09/09/2015 18:59, Oscar Benjamin wrote:
>> 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?
I wrote a small routine (below) to check when and if my code and the 
formula do match. It easily shows that
they only match for len(pool) == (2 ** N) - 1, with N greater or equal to 2.

My problem remains: WHY don't they match for every length? How did you 
build your 12-triples set? What's wrong with my algorithm?
And, most of all (and on topic, too): how can you build a Python program 
that builds your triples list?

Francesco

--------------------------------------------------------------------------------------------------------------------------------------

import pprint, itertools
poolbase = 
"abcdefghijklmnopqrstuvwxyz!ABCDEFGHIJKLMNOPQRSTUVWXYZ$0123456789"

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

def formula(sequence):
     dim = len(sequence)
     return (dim * (dim - 1) / 6)

matching = {}

for i in range(3, len(poolbase) + 1):
     pool = poolbase[:i]
     print("pool = %s:  -> '%s'" % (i, pool))
     combos = list(itertools.combinations(pool, 3))
     print("combos contains %s triples." % len(combos))

     triples = maketriples(combos)
     theory = formula(pool)

     print("maketriples(combos) yields %s triples." % len(triples))
     print("formula(pool) gives %s." % theory)
     if len(triples) == theory:
         pprint.pprint(triples)
         matching[len(pool)] = len(triples)
         input("\n--- Press Enter ---")
     print("-------------------------------------")

print("Dict of matching solutions and number of obtained triples:")
pprint.pprint(matching)