If you want to see the code, I just finished cleaning it a bit.
http://www.steinertriples.fr/ncohen/tmp/code.py
Nathann
On 14 September 2014 00:10, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Yoooooooooo !
>
> > Sounds like an interesting problem, do you know of an efficient
> algorithm to do this (without simply trying all sets of course)? Have you
> looked in the literature?
>
> I don't believe in "literature" anymore. I don't know a lot about other
> fields of research, but in graph theory people who say that they work on
> 'algorithms' apparently never heard of what a data structure is. All they
> care about is asymptotic complexity and whether their problem is
> polynomial/NP-Hard, especially on unheard-of classes of INPUT.
>
> What my implementation does is rather simple:
>
> 1) Think of all subsets of X, and say that the (unique) "predecessor" of a
> set S is S-{max(S)}. This is a graph.
> 2) Start from the empty set, and do a breadth-first search from there
> (this will explore all sets of size 1, then size 2, then [...])
> 3) For each set S that you explore, decide whether the set S already
> contains a set S' for which f(S') is False. In this case you know that f(S)
> is wrong without even calling S. If there is no such set then compute f(S).
> If it is true store the set somewhere, if it is wrong stop the exploration
> and keep this set S in the database of "NO" answers.
>
> The good thing here is that it is rather "quick" to test whether your
> current set S contains a set for which f was False. Just store all your
> "NO" sets in a binary matrix (i.e. an array of bitsets in Sage), and all
> you need to do to run the test is compute the intersection of some bitsets.
>
> There is no magic in the algorithm and it is 25 lines long. It is just a
> good way to avoid calling f too often when this function is very slow.
>
> Unfortunately it has been running for 10 hours on my computer and I still
> did not find the set I am looking for :-/
>
> > I have a "coding theory" feel about this problem because it sounds a bit
> like finding the minimal-weight vectors for a code (the sets X
> corresponding to the index sets of zero coefficients)
>
> NOooooooo idea about that O_o
>
> Nathann
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
