Re: looping over subsets

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Tue, Sep 12, 2006 at 04:44:33PM -0400, Igor Schein wrote:
> Hi,
> 
> 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?

Backtracking. You can do that in linear time in the number of subset which
is binomial(N,M).

forvec(,,2) can do it for you:
subsets(n,m)=forvec(x=vector(m,i,[i,i+n-m]),print(x),2)

? subsets(5,2)
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]

Cheers,
Bill