Re: [Axiom-mail] A combinatorial question

[Martin Rubey]

> On 10/2/07, Alasdair McAndrew wrote:
> > To experiment with a little algorithm, I need to generate all subsets of a
> > set S which have fixed cardinality; for example to generate all three
> > element subsets of {1,2,3,4,5,6,7}.  Is there an inbuilt command to do this
> > in Axiom?  Or has somebody written a package to do such a thing?

Well, the species package of Ralf and myself does that, of course.  But I'm not
sure whether it wouldn't be overkill for your purpose.  Also, although you can
use it from axiom, you need the Aldor compiler to install it.

If you only need subsets, than

In Aldor you'd say something like

  structures(set [1,2,3,4,5,6,7])$(Combination(3)(Integer))

in Axiom you would have to create the domain Combination(3)(Integer) first
using

  C3==>Interpret([parse "Combination(3)"], ACINT)

since Axiom cannot deal with signatures like the above.  Furthermore, since
Axiom doesn't understand Aldor's extend, you'll have to create the list of your
labels as follows:

  l := set([1,2,3,4,5,6,7]::ACList INT)$SetSpecies ACINT

Now you can indeed say

  structures(l)$C3

and step through the subsets.

Otherwise, and especially if you only need subsets, I'd roll my own, just as
Bill did.  It depends a bit on how far you need to go.  If you google for
"Ruskey, combinatorial generation", you'll find RuskeyCombGen.pdf which
contains algorithms that are relatively easy to implement.

(In fact, Combination from the species project currently also uses a dumb
algorithm.)

If you are interested in the species approach, please do not hesitate to ask
for more explanations.

Martin