The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
CM-Permutation-0.94
++
/ CM::Group::Sym

NAME

CM::Group::Sym - An implementation of the finite symmetric group S_n

VERSION

version 0.94

DESCRIPTION

CM::Group::Sym is an implementation of the finite Symmetric Group S_n

SYNOPSIS

    use CM::Group::Sym;
    my $G1 = CM::Group::Sym->new({n=>3});
    my $G2 = CM::Group::Sym->new({n=>4});
    $G1->compute();
    $G2->compute();

This way you will generate S_3 with all it's 6 elements which are permutations. Say you want to print the operation table(Cayley table).

    print $G1

    6 5 4 3 2 1
    3 4 5 6 1 2
    2 1 6 5 4 3
    5 6 1 2 3 4
    4 3 2 1 6 5
    1 2 3 4 5 6

or the table of S_4 with 24 elements

    print $G2

    24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
    23 24 20 16 22 18 19 15 21 17 13 14 11 12  8  4 10  6  7  3  9  5  1  2
    22 18 19 15 23 24 20 16 11 12  8  4 21 17 13 14  9  5  1  2 10  6  7  3
    21 17 13 14  9  5  1  2 10  6  7  3 22 18 19 15 23 24 20 16 11 12  8  4
    20 19 18 17 24 23 22 21 12 11 10  9 16 15 14 13  4  3  2  1  8  7  6  5
    19 20 24 12 18 22 23 11 17 21  9 10 15 16  4  8 14  2  3  7 13  1  5  6
    18 22 23 11 19 20 24 12 15 16  4  8 17 21  9 10 13  1  5  6 14  2  3  7
    17 21  9 10 13  1  5  6 14  2  3  7 18 22 23 11 19 20 24 12 15 16  4  8
    16 15 14 13  4  3  2  1  8  7  6  5 20 19 18 17 24 23 22 21 12 11 10  9
    15 16  4  8 14  2  3  7 13  1  5  6 19 20 24 12 18 22 23 11 17 21  9 10
    14  2  3  7 15 16  4  8 19 20 24 12 13  1  5  6 17 21  9 10 18 22 23 11
    13  1  5  6 17 21  9 10 18 22 23 11 14  2  3  7 15 16  4  8 19 20 24 12
    12 11 10  9  8  7  6  5  4  3  2  1 24 23 22 21 20 19 18 17 16 15 14 13
    11 12  8  4 10  6  7  3  9  5  1  2 23 24 20 16 22 18 19 15 21 17 13 14
    10  6  7  3 11 12  8  4 23 24 20 16  9  5  1  2 21 17 13 14 22 18 19 15
     9  5  1  2 21 17 13 14 22 18 19 15 10  6  7  3 11 12  8  4 23 24 20 16
     8  7  6  5 12 11 10  9 24 23 22 21  4  3  2  1 16 15 14 13 20 19 18 17
     7  8 12 24  6 10 11 23  5  9 21 22  3  4 16 20  2 14 15 19  1 13 17 18
     6 10 11 23  7  8 12 24  3  4 16 20  5  9 21 22  1 13 17 18  2 14 15 19
     5  9 21 22  1 13 17 18  2 14 15 19  6 10 11 23  7  8 12 24  3  4 16 20
     4  3  2  1 16 15 14 13 20 19 18 17  8  7  6  5 12 11 10  9 24 23 22 21
     3  4 16 20  2 14 15 19  1 13 17 18  7  8 12 24  6 10 11 23  5  9 21 22
     2 14 15 19  3  4 16 20  7  8 12 24  1 13 17 18  5  9 21 22  6 10 11 23
     1 13 17 18  5  9 21 22  6 10 11 23  2 14 15 19  3  4 16 20  7  8 12 24

Note that those are only labels for the elements as printing the whole permutations would render the table useless since they wouldn't fit. You can find that for S_5 the table would not fit on the screen (or maybe it would if you had a big enough screen, or a small enough font).

You can also see a coloured Cayley table(the labels of the permutations are associated to colours):

So if you want to see the meaning of the numbers(the permutations behind them) you can use str_perm()

    print $G1->str_perm;

    1 -> 3 2 1
    2 -> 2 3 1
    3 -> 2 1 3
    4 -> 3 1 2
    5 -> 1 3 2
    6 -> 1 2 3

conj_classes()

find the conjugacy classes using the definition of conjugates.

conj_classes_fast()

finds the conjugacy classes of a group using cycle structure. for example, the conjugacy classes of S_4 correspond to partitions of the number 4:

    (x)(x)(x)(x)
    (xx)(x)(x)
    (xx)(xx)
    (xxx)(x)
    (xxxxx)

so S_4 has 5 conjugacy classes.

compute()

Computes the operation table.

draw_diagram($path)

This method will draw a diagram of the group to png to the given $path. You can read the graph as follows. An edge from X to Y with a label Z on it that means X * Z = Y where X,Y,Z are labels of permutations.

identity()

return the identity permutation for this group

centralizer(element)

this method returns the centralizer of an element in the group. (note that the centralizer can be different in some particular subgroup)

center()

returns the center of the group

normal_subgroups()

computes the normal subgroups of a group of permutations

dimino(@S)

given a set of generators @S , Dimino's algorithm(see [2] for details) enumerates all elements of the subgroup <@S> generated by the set @S

cayley_digraph($path,$generators_arrayref)

computes the Cayley graph of a group given the generators.

for example the graph for S_4 with generators the transpositions (1,2) ; (2,3) ; (3,4) looks like this:

Fortunately this particular cayley graph can be arranged as a truncated octahedron and it's one of the 13 Archimedian solids , it's also called a permutahedron.

THEOREMS AS TESTS

Some theorems and properties of groups or permutations are used as tests.

BIBLIOGRAPHY

    [1] Joseph Rotman   - An Introduction to the Theory of Groups
    [2] Gregory Butler  - Fundamental Algorithms for Permutation Groups (Lecture Notes in Computer Science)
    [3] http://www.jaapsch.net/puzzles/cayley.htm

SEE ALSO

http://en.wikipedia.org/wiki/Permutohedron

http://en.wikipedia.org/wiki/Archimedean_solid

http://en.wikipedia.org/wiki/Truncated_octahedron

http://en.wikipedia.org/wiki/Cayley_graph

AUTHOR

Stefan Petrea, <stefan.petrea at gmail.com>