> I have no idea how to generate the isomorphism types of a functorial
> composition, not even inefficiently...
Isomorphim types are equivalence classes. Each structure is a finite
object. There are only finitely many objects of a given size. So a
stupid algorithm is:
isomorphismTypes(s: SetSpecies L): Generator % == generate {
empty? s => ...
labels: SetSpecies L := set([first s for x in s]$List(L)); -- (*)
s: Set % := [structures labels];
for x in s repeat yield x;
}
Of course that algorithm needs lots and lots and lots of memory, but
theoretically it's simple.
You certainly see the dirty trick (*). I basically pretend that
something like [1,1,1,1] is a SetSpecies. Which of course is a big lie
and really makes me think of going back to the design of having a List
as the argument type of "isomorphismTypes" and "structures".
After reading Martin's mails several times, I think, he made a good
point. There is not only "structures" and "isomorphismTypes". There are
many things inbetween.
So for the design of AC I would like to propose the following.
structures: List L -> Generator %
isomorphismTypes: List L -> Generator %
with the following interpretation:
Let F be a species and U be a list (all elements of the same type L),
n=card(U). Then there is a bijection
sigma: {1,...,n} -> U.
Then structures(U) should return a generator g that generates the
elements F[sigma](z) where z runs over all elements of F[{1,...,n}].
If all element of U are distinct, then g generates F[U] where U is
considered as a set.
If the list U is considered as a multiset then still structures(U)
generates card(F[{1,...,n}]) elements.
In turn isomorphismTypes(U) returns a generator y that generates only
*distinct* elements of F[sigma](z) where z runs over all elements of
F[{1,...,n}]. (So this might give fewer elements.)
If all element of U are distinct, then y generates F[U] where U is
considered as a set.
However, contrary to "structures(U)" isomorphismTypes(U) returns
isomorphism classes.
For unlabelled generation, we apply S_n to form the cosets. So it is
basically computing coset representatives of F[{1,...,n}] "modulo S_n".
For the intermediate case that Martin is talking about, a multiset just
corresponds to a subgroup of S_n.
I somehow have the feeling that must have something to do with the cycle
indicator series, no?
You might now ask, since isomorphismTypes can also generate *all*
structures, why would we need both "structures" and "isomorphismTypes"?
I don't know exactly, but I somehow have the feeling that "structures"
is often easier since there is no need to check for isomorphy/equality.
So it would be a little more efficient if such a test need not be done.
But maybe this approach also answers Martin's approach of wanting a
different representation for the generated isomorphismTypes. I don't
think that is necessary. I like more the approach to consider them as
coset representatives.
What is your opinion?
Ralf
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
