Petrea Corneliu Ştefan > CM-Permutation-0.94 > CM::Group::Sym

Download:
CM-Permutation-0.94.tar.gz

Dependencies

Annotate this POD

CPAN RT

Open  0
View/Report Bugs
Module Version: 0.94   Source  

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>

syntax highlighting: