On 15/09/2015 23.14, Francesco A. Loffredo wrote:
On 14/09/2015 13:50, Oscar Benjamin wrote:
... Your algorithm loops through all triples and accepts any
triple if it doesn't immediately conflict with any of the
triples already accepted.
If you were solving a sudoku puzzle then an analogous algorithm
would
take each empty square and fill it with any number that doesn't
contradict any of the currently filled squares. If you try this on a
real puzzle then you will reach a dead end and you won't fill the
grid. The problem is that some of the squares you filled in
could have
had a number of possible values and you've just chosen them
arbitrarily (and incorrectly).
...
Also there will be many possible solutions and you only really
need to
find one. Up to isomorphism there is 1 solution for N=9 but that
means
there will be 9! isomorphic solutions (the number of ways of
relabelling the numbers 1 through 9). This means that you may
not have
to go far in the search before coming across a solution.
--
Oscar
Thank you for your explanation, Oscar! I'll study a better algorithm
and I'll post it here. While I hope Marcus Luetolf ( the OP) will
find it useful, I will certainly get some learning from this exercise.
Still thinking about it. I have read about Steiner systems and the
Social Golfer problem, and I'm afraid this will remain an Unsolved
Problem despite my efforts. Up to now, I thought that backtracking can't
be a solution, unless I can rethink my algorithm as a tree traversal.
Problem is, when you arrive at the end of the combos list and you
discover you hit a dead end, how can you choose which triple you should
change?
One possible solution is a non-deterministic one: instead of reading the
list in order, I could shuffle it. And if my solution doesn't match the
formula, I could simply repeat the random reading of the list. As you
said, <<you may not have to go far in the search before coming across a
solution>>!
Of course, dear Tutors, if some of you can think a way to educate my
guessing, you're more than welcome!
Here is my current algorithm:
import pprint, itertools, random, math
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)
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))
now_quit = 100 * len(combos)
matching = False
tries_count = 0
theory = formula(pool)
while not matching:
triples = maketriples(random.sample(combos, len(combos)))
tries_count += 1
matching = (len(triples) == theory)
if matching:
print("Found a match after %s tries!" % tries_count)
else:
if not (tries_count % (10 ** int(math.log(tries_count, 10)))):
print("Tried %s times..." % tries_count)
if tries_count > now_quit:
print("Reached %s tries, now quitting!" % tries_count)
break
print("maketriples(combos) yields %s triples." % len(triples))
print("formula(pool) gives %s." % theory)
if matching:
pprint.pprint(triples)
input("\n--- Press Enter ---")
else:
print("\n\n")
print("-------------------------------------")
---------------------------
Francesco
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
