Karim Belabas on Tue, 12 Sep 2006 23:40:46 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: looping over subsets 

* Igor Schein [2006-09-12 22:46]:
> what's the most efficient (subexponential in N) way to loop over all
> subsets with cardinality M of a set with cardinality N, M<=N?

You can do it in linear time wrt the output size ( = binomial(N,M) ), see

  http://www.math.u-bordeaux.fr/~belabas/pari/doc/faq.html#loopsubsetspart

Note that for M = N/2, where binomial(N,M) is largest for given N, the
output size is essentially 2^N. This won't be subexponential in N...

Cheers,

    K.B.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`