Hi Simon, Nathann,
On Mon, Apr 15, 2013 at 11:17:14AM +0000, Simon King wrote:
> On 2013-04-15, Simon King <simon.k...@uni-jena.de> wrote:
> > I have a finite set X and a set S of subsets of X. I'd like to get a
> > list (or better: an iterator) of all subsets U of S (i.e., subsets of
> > subsets) such that the union of the elements of U is equal to X.
> > Ideally, I'd like that the number of intersection points (counted with
> > multiplicity) of elements of U is ascending.
> >
> > Hence, if there is a disjoint cover of X by elements of S, then I'd like
> > to get this first, and otherwise I'd like to first get a cover that is "as
> > close to being disjoint as possible".
>
> I have found that one can get disjoint ("exact") covers via "dancing
> links".
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
As for iterating: Nathann, I haven't been following up on this one; do
you know what's the current status of this feature?
On a related note: Serge Guelton is working on Python bindings for the
ISL library, which might have this kind of features. Last time I got
in touch, he was considering coming to the Sage-Combinat days in June.
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
