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)
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
