Re: [Axiom-mail] A combinatorial question

[martin . rubey]

<address@hidden>
<address@hidden>
<address@hidden> Gcc:
nnml:mail.axiom
From: Martin Rubey <address@hidden>
Date: 04 Oct 2007 08:23:51 +0200
In-Reply-To: <address@hidden>
Message-ID: <address@hidden>
Lines: 47
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
--text follows this line--
"Bill Page" <address@hidden> writes:

> (1) -> )set message time on
> (1) -> a:=[subSet(25,5,i) for i in 0..binomial(25,5)-1];
> (1) ->
>                                                       Type: List List Integer
>                                      Time: 58.00 (EV) + 6.61 (GC) = 64.61 sec
> 
> This works but obviously it should be possible to write an algorithm that
> performs better than this ... :-( Sage can do it in less than a second (via
> GAP) and apparently Mathematica can do it in about 0.04 seconds!

As I said before (but maybe my message didn't get through), good algorithms are
described in Ruskey (google: "Ruskey, combinatorial generation", goto
RuskeyCombGen.pdf)

If you are indeed interested in such things, PLEASE consider joining the
species project.  Much work has already been done, and since Aldor is semi-free
now, I think it was not a wasted effort.  Note also that the framework provided
by the species project is very general - it becomes very easy to build new
structures from old.

We have some big problems, which we probably should be open about:

* apart from Ralf and myself, we have no users so far.  Well, we didn't
  advertise it either.  This is where you could help.

The other problems have to do with Aldor - Axiom internals.  I'll still mention
them here:

* Axiom does not support Aldor's extend construct.  I.e., one cannot say

  #include "axiom"
  extend Integer: LabelType == add ...

  which makes some ugly - user visible - workarounds necessary.  Enabling that
  would be wonderful.

* Axiom does not support general signatures like

  Combination(k: Integer)(L: LabelType): CombinatorialSpecies(L) with { ... }

  Again, we provide a workaround.  I expect a real fix to be rather hard, here.

Martin