Enumerating partitions of polyhedron vertices
QF
that enumerates partitionings of P's vertices into n sets (where n<=3),
up to isomorphism in G?
That is to say, each partition contains up to 3 disjoint sets of
vertices, and partitionings that are isomorphic (up to
rotation/reflection/etc., as given by G) should only be listed once.
So far the only thing I can think of is to enumerate the partitions of
the number V of vertices and exclude those that have more than 3 sets.
But I'm not sure how to efficiently exclude isomorphic partitionings.
Since I'm dealing with polyhedra with a high degree of symmetry (such as
Platonic solids), |G| is potentially quite large, and it would be nice
if the algorithm could somehow take advantage of this.
Chip Eastham
One approach is to impose a lexicographic ordering
the way partitions are represented. One then has
an effective choice of representative of classes
equivalent up to isomorphism as being the least
such element under the given ordering.
For example a partition can be represented as a
list of vertex labels, say 1,...,v, together
with "separator symbols" 0 that occur n-1 times
(if there are n sets in the partition). All
the labels before the first appearance of 0
constitute one set, the labels between the
first and second constitute another set, and
so on.
Apart from the action by symmetry group G
it is pretty easy to determine a least
representative, through permutation of
the n sets and the elements within each
such set. Namely the first set is that
which contains label 1 (and is listed in
ascending order), the second set is that
which contains the least element not in
the first set (and thereafter is listed
in sorted order), and so on.
The effect of symmetry group G can then
be incorporated in a "brute force" way
by generating the lexicographic least
representatives of partitions without
regard to equivalence by G, and checking
each permutation induced by element g
in G to see if the respective listing
admits a lowered ordering.
regards, chip