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

[Francesco A. Loffredo]

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