Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!manuel!csc.anu.edu.au!bdm659
From: bdm659@csc.anu.edu.au
Newsgroups: comp.theory
Subject: Generating subsets which are not supersets
Message-ID: <1991May18.120016.1@csc.anu.edu.au>
Date: 18 May 91 01:00:16 GMT
Sender: news@newshost.anu.edu.au
Organization: Computer Services, Australian National University
Lines: 10

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.

Brendan McKay.   Australian National University.