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

[Oscar Benjamin]

On 21 September 2015 at 22:54, Francesco A. Loffredo <fal at libero.it> wrote:
>>
> 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?

I would remove the last one added and then loop over all triples
starting from the one after that. I have written a simple
implementation below. The problem is that it's really slow for
anything more than N=9. There are many ways it can be improved though
if you want it to scale to higher levels:

#!/usr/bin/env python

from itertools import permutations, combinations
import pprint, itertools

def get_triples(labels):
    Nlabels = len(labels)
    if Nlabels % 6 not in (1, 3):
        raise ValueError("No exact solution")

    target = (Nlabels * (Nlabels - 1)) // 6

    all_triples = list(combinations(labels, 3))
    Ntriples = len(all_triples)

    triples = []
    pairs = set()

    start_index = 0
    while True:
        for index in range(start_index, Ntriples):
            triple = all_triples[index]

            # If the triple fits try it out and see what happens...
            if not any(p in pairs for p in combinations(triple, 2)):
                triples.append((triple, index))
                pairs.update(permutations(triple, 2))

                # Success!
                if len(triples) == target:
                    return [triple for triple, _ in triples]
        else:
            # We tried every combination of the current triples
            # and all subsequently available triples. Time to
            # pop off the triple at the top and look for another
            # one to replace it.
            triple, start_index = triples.pop()
            pairs.difference_update(permutations(triple, 2))
            # Start from the triple after the popped one.
            start_index += 1


if __name__ == "__main__":
    import sys
    Nlabels = int(sys.argv[1])
    labels = range(1, Nlabels + 1)
    triples = get_triples(labels)
    pprint.pprint(triples)


To improve on this I would probably work on it as a constraint
propagation problem rather than looping over all the combinations. The
problem with backtracking on the full set of combinations is that it
grows combinatorially which means it gets complicated very quickly as
N increases. For N=9 this ran in 50ms. At the time of writing I'm
still waiting for it to finish N=13 under pypy (it's only been a
couple of minutes). I don't know if I expect it to finish in a few
seconds or take longer than the age of the universe.


--
Oscar