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

[Oscar Benjamin]

On 10 September 2015 at 08:45, Francesco Loffredo via Tutor
<tutor at python.org> wrote:
>
> 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.

That's interesting. I'm not sure exactly why that would happen.

> My problem remains: WHY don't they match for every length?

Your algorithm is not generally guaranteed to find a full solution.

> How did you build your 12-triples set?

I took it from this diagram:
https://upload.wikimedia.org/wikipedia/commons/e/eb/Hesse_configuration.svg

> 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?

Perhaps if we compare this problem to a different problem then we can
see how your algorithm may not be optimal. Imagine solving a sudoku
puzzle.

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).

The solution for a sudoku solving algorithm would be to back-track.
One of the previously filled squares was filled incorrectly so go back
and change what you had before. As a recursive algorithm you would
take an unfilled square, loop over the possible values that it can
take and for each of those values attempt to fill the remainder of the
sudoko grid.

The analogous backtracking algorithm for this problem would mean
deciding first to include a particular triple if it is compatible with
the already accepted triples and then continuing with the remaining
triples to see if it leads to a full set (you know how big a full set
should be). If it does not lead to a full set then you were wrong to
include one of your current triples so now decide not to include it
and again loop through the remaining triples looking for a full set.

I imagine that the complexity of this algorithm will grow rapidly as N
increases. For N=9 you have thousands of triples, so the powerset of
this has 2**N members meaning that this binary backtracking algorithm
has a very large space to explore. The space is heavily pruned by the
pairing constraint though so it may not work out as badly as I expect.

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