Article View: comp.theory
Article #1666Re: Generating subsets which are not supersets
From: Andre Marien
Date: Thu, 23 May 1991 08:59
Date: Thu, 23 May 1991 08:59
24 lines
1323 bytes
1323 bytes
In article <1991May18.120016.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes:
>Let S = {1,2,...,n}, and suppose that X[1],...,X[k] are subsets of S.
>
>I wish to generate all the subsets of S which are not supersets of
>any X[i]. In a typical application, n will be about 20, k will be
>100-1000 and the X[i] will have size 3-5.
>
>Does anyone know how this can be done fast? Practical performance
>is more important than theoretical nicety. Thanks.
reformulation:
X[1] = { a1, a2, , am1 }
becomes:
C[1] = ~p1 v ~p1 v ... v ~p1
1 2 m1
The problem becomes:
find all models M for C[1],...,C[k]
So, there is a lot of literature on this problem, but no always efficient algorithm.
Andre' Marien
bimandre@cs.kuleuven.ac.be
Technical Details
Message-ID:
<3545@n-kulcs.cs.kuleuven.ac.be>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ub4b!kulcs!icarus.cs.kuleuven.ac.beReferences:
<1991May18.120016.1@csc.anu.edu.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!ub4b!kulcs!icarus.cs.kuleuven.ac.be From: bimandre@icarus.cs.kuleuven.ac.be (Andre Marien) Newsgroups: comp.theory Subject: Re: Generating subsets which are not supersets Message-ID: <3545@n-kulcs.cs.kuleuven.ac.be> Date: 23 May 91 08:59:15 GMT References: <1991May18.120016.1@csc.anu.edu.au> Sender: news@cs.kuleuven.ac.be Organization: Dept. of Computer Science (K.U.Leuven) Lines: 24 Originator: bimandre@icarus