Hello Gary,
I am the guy who wrote this stuff about enumeration modulo the action of
a permutation group.
Your problem completely enter the current sage engine of enumeration
modulo a permutation group.
Imagine you want to enumerate all sets of 5 tuples each being composed
with 3 elements of the finite field with 3 elements. This corresponds to
the permutation group acting on cols and rows of a rectangular matrix of
size 3*5. If I give the entries of such matrices the following numeration
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15
The permutation group is thus generated by :
[[(1, 4), (2, 5), (3, 6)], # swap the 2 first cols
[(1, 4, 7, 10, 13), (2, 5, 8, 11, 14), (3, 6, 9, 12, 15)], # circular
swap of cols
[(1, 2), (4, 5), (7, 8), (10, 11), (13, 14)], # swap the 2 first rows
[(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)]] #
circular swap of rows
In top of that, the current engine of enumeration modulo a permutation
group admit an extra parameter which is 'max_part' (this option was also
a Dima's suggestion when I meet him at Orsay (next to Paris...)). Now
imagine a prime number p, your set is just a kind of matrix I just
described with integer entries in {0, 1, ... , p-1}. You have the group
and the max_part, you can enumerate...
To be perfect, you would like to recover sets of tuples of finite field
elements and not integer vectors of length 15 with non negative entries
lower than p. So you just have to define a post_process (This part is a
little bit technical but appears to be very very very common in
combinatorics). Here the post_process is just a Python function which
transform a very long tuples of integers in {0, 1, ... , p-1} into the
proper set you want. As my English is not perfect, please read the code
(post_process allows to manipulate a special set internally but provide
a different flavors of front-end user elements...) :
def post_process_func(self, T):
r"""
This function converts an integer vector of length
``card*length`` whose entries is in `{0,1,...,char-1}` into a
set of ``card`` tuples of length ``length`` whose entries are
element of the finite field containing ``char`` elements.
"""
S = set([])
for i in range(self._card):
S.add( tuple(self.ambient_field()(T[j]) for j in
range(i*self._length, (i+1)*self._length)) )
if len(S) == self._card:
return S
else:
return None
Ok, this is not easy if you begin with Sage... I just attach a file to
this mail which can probably solve your problem (And you will probably
better understand the post_process with the context...) :
sage: load "Math/Sage_personnel/set_of_tuple_of_finite_field.py"
sage: S = SetTupleFiniteFieldElement(3, 5, 3, verbose=True)
[[(1, 4), (2, 5), (3, 6)]]
[[(1, 4, 7, 10, 13), (2, 5, 8, 11, 14), (3, 6, 9, 12, 15)]]
[[(1, 2), (4, 5), (7, 8), (10, 11), (13, 14)]]
[[(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)]]
sage: it = iter(S)
sage: it.next()
set([(1, 0, 0), (0, 1, 0), (0, 0, 0), (0, 0, 1), (2, 0, 0)])
sage: it.next()
set([(1, 0, 0), (1, 1, 0), (0, 1, 0), (0, 0, 0), (0, 0, 1)])
sage: it.next()
set([(1, 0, 0), (0, 0, 1), (0, 1, 0), (0, 0, 0), (2, 1, 0)])
sage: it.next()
set([(1, 0, 0), (1, 1, 0), (0, 1, 0), (0, 0, 0), (2, 0, 0)])
sage: it.next()
set([(1, 0, 0), (1, 1, 0), (0, 0, 0), (0, 0, 1), (2, 0, 0)])
sage: it.next()
set([(1, 1, 0), (0, 1, 0), (0, 0, 0), (0, 0, 1), (2, 0, 0)])
sage: S.cardinality()
14066
---> At the end, you will get a king of deg lex order for the
enumeration. Be careful, Python's sets reorder tuples...
It uses strongly the IntegerVectorsModPermgroup features and the
SearchForest feature. The post_process is a nice request from Florent
Hivert. So you have severals contributors to thanks and finally, I think
that Sage contains all the features you need to solve your problem.
However, I found relatively difficult to plug them together during the
two last hours I spent to try implement the small Python class attached
in the file.
I am quite very busy these days but feel free to ask for further details
about all these features. Sorry for delay of answer and I can't promise
better in the days to come but I will try to read the combinat list
regulary. I will be also very happy that my small work originally
motivated by invariants theory could help you in your research.
Cheers,
Nicolas B. (The little Nicolas...)
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
#***
#
# Enumerating set of tup
