[Aldor-l] [Axiom-mail] A combinatorial question

[martin.rubey at univie.ac.at]

<fbcd16d40710021736o863cb50v4c6e2b09409925ca at mail.gmail.com>
<1d67a53c0710021740y5150fc8n538b6cc75e4a47f7 at mail.gmail.com>
<fbcd16d40710031842t7c2bb11ase97a0527f83d147b at mail.gmail.com> Gcc:
nnml:mail.axiom
From: Martin Rubey <martin.rubey at univie.ac.at>
Date: 04 Oct 2007 08:23:51 +0200
In-Reply-To: <fbcd16d40710031842t7c2bb11ase97a0527f83d147b at mail.gmail.com>
Message-ID: <9qtzp7o0so.fsf at aquin.mat.univie.ac.at>
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" <bill.page at newsynthesis.org> 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