On 10 September 2015 at 08:45, Francesco Loffredo via Tutor <tutor@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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor