[Tutor] Creating lists with definite (n) items without repetitions
Francesco A. Loffredo
fal at libero.it
Tue Sep 15 23:14:29 CEST 2015
On 14/09/2015 13:50, Oscar Benjamin wrote:
> 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).
>
>
> ...
> 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.
Francesco
More information about the Tutor
mailing list