More help requested on permutation code.

Discussion in 'Perl Misc' started by Michael Press, Mar 24, 2006.

  1. Thank you all for the help. Would you guys look at
    the rest of the code? First a disclaimer.
    The sort assumes numerical permutation elements.
    This is a limitation I can rectify.

    ________________CUT________________
    #! /usr/bin/perl

    use warnings;
    use strict;

    # Multiply permutation cycles, into a permutation map;
    # then turn the map into a cycle representation, and print.
    # Knuth ACP 1.3.3 Algorithm B.

    sub permutation_multiply
    {
    my $t;
    my $hold;
    my $prev;

    # Read in the cycles, and initialize the permutation array.
    my %permutation_map = map { /\w/ ? ( $_ => $_ ) : () } my @token_list = $_[0] =~ /\w+|[()]/g;

    # Multiply the cycles generating the permutation as a map.
    for (my $idx = $#token_list; $idx >= 0; --$idx)
    {
    my $it = $token_list[$idx];
    if ($it eq ')' ) { $prev = $it }
    elsif ($it eq '(' ) { $permutation_map{$hold} = $prev }
    else
    {
    if ( $prev eq ')' ) { $hold = $it }
    $t = $prev, $prev = $permutation_map{$it}, $permutation_map{$it} = $t;
    }
    }

    # Generate the cycle representation from the permutation in %permutation_map
    my @cycles;
    for my $key (sort { $a <=> $b } keys %permutation_map)
    {
    my @element_list;
    next if $permutation_map{$key} =~ m/-$/ ;
    do
    {
    push @element_list, $key;
    $t = $permutation_map{$key};
    $permutation_map{$key} .= '-';
    $key = $t;
    } while ($permutation_map{$key} !~ m/-$/ );
    push @cycles, [@element_list];
    }
    for my $key (keys %permutation_map) {$permutation_map{$key} =~ tr/-//d }

    # Print out the cycles:
    # Sort the cycles by length.
    # Put spaces between permutation elements.
    # Put in cycle delimiter parentheses.
    # Put spaces between permutation cycles.
    # Print.
    print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a} <=> $#{$b}} @cycles ), "\n";
    }

    my $alpha = "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)";
    my $beta = "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22 21 19)";
    my $gamma = "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)(10 16)(12 21)(14 18)";
    my $delta = "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11 19 22 14 17)";
    my $x;

    print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma alpha^18 \n";
    $x = ($alpha x 5 . $gamma) x 2 . $alpha x 14 . $gamma . $alpha x 18;
    permutation_multiply $x;
    $x = $beta;
    permutation_multiply $x;
    print "\n";

    print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    $x = (($alpha x 13) . $gamma . ($delta x 2)) x 3;
    permutation_multiply $x;
    print "\n";

    ________________END________________

    --
    Michael Press
     
    Michael Press, Mar 24, 2006
    #1
    1. Advertising

  2. Michael Press wrote:
    > Thank you all for the help. Would you guys look at
    > the rest of the code? First a disclaimer.
    > The sort assumes numerical permutation elements.
    > This is a limitation I can rectify.
    >
    > ________________CUT________________
    > #! /usr/bin/perl
    >
    > use warnings;
    > use strict;
    >
    > # Multiply permutation cycles, into a permutation map;
    > # then turn the map into a cycle representation, and print.
    > # Knuth ACP 1.3.3 Algorithm B.
    >
    > sub permutation_multiply
    > {
    > my $t;
    > my $hold;
    > my $prev;
    >
    > # Read in the cycles, and initialize the permutation array.
    > my %permutation_map = map { /\w/ ? ( $_ => $_ ) : () } my @token_list = $_[0] =~ /\w+|[()]/g;
    >
    > # Multiply the cycles generating the permutation as a map.
    > for (my $idx = $#token_list; $idx >= 0; --$idx)
    > {
    > my $it = $token_list[$idx];


    In Perl that is usually written as:

    for my $it ( reverse @token_list ) {

    > if ($it eq ')' ) { $prev = $it }
    > elsif ($it eq '(' ) { $permutation_map{$hold} = $prev }
    > else
    > {
    > if ( $prev eq ')' ) { $hold = $it }
    > $t = $prev, $prev = $permutation_map{$it}, $permutation_map{$it} = $t;


    In Perl that is usually written as:

    ( $prev, $permutation_map{$it} ) = ( $permutation_map{$it}, $prev );

    > }
    > }
    >
    > # Generate the cycle representation from the permutation in %permutation_map
    > my @cycles;
    > for my $key (sort { $a <=> $b } keys %permutation_map)
    > {
    > my @element_list;
    > next if $permutation_map{$key} =~ m/-$/ ;


    It _may_ be better to use substr() there (YMMV):

    next if substr( $permutation_map{$key}, -1 ) eq '-';

    > do
    > {
    > push @element_list, $key;
    > $t = $permutation_map{$key};
    > $permutation_map{$key} .= '-';
    > $key = $t;
    > } while ($permutation_map{$key} !~ m/-$/ );
    > push @cycles, [@element_list];
    > }
    > for my $key (keys %permutation_map) {$permutation_map{$key} =~ tr/-//d }


    In Perl that is usually written as:

    tr/-//d for values %permutation_map;

    > # Print out the cycles:
    > # Sort the cycles by length.
    > # Put spaces between permutation elements.
    > # Put in cycle delimiter parentheses.
    > # Put spaces between permutation cycles.
    > # Print.
    > print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a} <=> $#{$b}} @cycles ), "\n";


    Unless you have changed the value of the $" variable you could write that as:

    print join( ' ', map "(@$_)", sort { @$a <=> @$b } @cycles ), "\n";

    Or, to extend that to the next level: :)

    print "@{[ map "(@$_)", sort { @$a <=> @$b } @cycles ]}\n";

    > }
    >
    > my $alpha = "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)";
    > my $beta = "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22 21 19)";
    > my $gamma = "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)(10 16)(12 21)(14 18)";
    > my $delta = "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11 19 22 14 17)";
    > my $x;
    >
    > print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma alpha^18 \n";
    > $x = ($alpha x 5 . $gamma) x 2 . $alpha x 14 . $gamma . $alpha x 18;
    > permutation_multiply $x;
    > $x = $beta;
    > permutation_multiply $x;
    > print "\n";
    >
    > print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    > $x = (($alpha x 13) . $gamma . ($delta x 2)) x 3;
    > permutation_multiply $x;
    > print "\n";
    >
    > ________________END________________



    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Mar 24, 2006
    #2
    1. Advertising

  3. John W. Krahn wrote:
    > Michael Press wrote:
    >>
    >> print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a} <=> $#{$b}} @cycles ), "\n";

    >
    > Unless you have changed the value of the $" variable you could write that as:
    >
    > print join( ' ', map "(@$_)", sort { @$a <=> @$b } @cycles ), "\n";
    >
    > Or, to extend that to the next level: :)
    >
    > print "@{[ map "(@$_)", sort { @$a <=> @$b } @cycles ]}\n";


    Oops, correction: :)

    print "@{[ map qq[(@$_)], sort { @$a <=> @$b } @cycles ]}\n";


    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Mar 24, 2006
    #3
  4. In article <aHLUf.1707$B_1.825@edtnps89>,
    "John W. Krahn" <> wrote:

    > Michael Press wrote:


    [...]

    > > for (my $idx = $#token_list; $idx >= 0; --$idx)
    > > {
    > > my $it = $token_list[$idx];

    >
    > In Perl that is usually written as:
    >
    > for my $it ( reverse @token_list ) {


    I chose not to use `reverse' because I do not want a reversed list,
    and reversing a list takes time. Yes? Or does Perl understand
    the context and simply feed me the elements in reverse order?

    [...]

    > > $t = $prev, $prev = $permutation_map{$it}, $permutation_map{$it} = $t;

    >
    > In Perl that is usually written as:
    >
    > ( $prev, $permutation_map{$it} ) = ( $permutation_map{$it}, $prev );


    I knew that. :)

    [...]

    > > next if $permutation_map{$key} =~ m/-$/ ;

    >
    > It _may_ be better to use substr() there (YMMV):
    >
    > next if substr( $permutation_map{$key}, -1 ) eq '-';


    Noted. This is preferable for me and my style.

    [...]

    > > push @cycles, [@element_list];
    > > }
    > > for my $key (keys %permutation_map) {$permutation_map{$key} =~ tr/-//d }

    >
    > In Perl that is usually written as:
    >
    > tr/-//d for values %permutation_map;


    Nifty. Another Perl right to left pipeline.


    [...]

    > > print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a} <=> $#{$b}} @cycles ), "\n";

    >
    > Unless you have changed the value of the $" variable you could write that as:
    >
    > print join( ' ', map "(@$_)", sort { @$a <=> @$b } @cycles ), "\n";
    >
    > Or, to extend that to the next level: :)
    >
    > print "@{[ map "(@$_)", sort { @$a <=> @$b } @cycles ]}\n";


    So what is with the square brackets?
    Capture the list with a reference,
    then dereference in the print statement to interpolate $".
    Yes?

    [...]

    I also see the

    print "@{[ map qq[(@$_)], sort { @$a <=> @$b } @cycles ]}\n";

    from your follow up article. Elegant.

    Looking at other folks exemplary code is valuable.
    Seeing changes to code that I worked over is liberating.
    Thanks.

    --
    Michael Press
     
    Michael Press, Mar 24, 2006
    #4
  5. Michael Press wrote:
    > In article <aHLUf.1707$B_1.825@edtnps89>,
    > "John W. Krahn" <> wrote:
    >
    >>Michael Press wrote:

    >
    > [...]
    >
    >>> for (my $idx = $#token_list; $idx >= 0; --$idx)
    >>> {
    >>> my $it = $token_list[$idx];

    >>In Perl that is usually written as:
    >>
    >> for my $it ( reverse @token_list ) {

    >
    > I chose not to use `reverse' because I do not want a reversed list,
    > and reversing a list takes time. Yes? Or does Perl understand
    > the context and simply feed me the elements in reverse order?


    I was just presenting the usual Perl idiom. Your way may in fact be better.
    :)

    >>> push @cycles, [@element_list];
    >>> }
    >>> for my $key (keys %permutation_map) {$permutation_map{$key} =~ tr/-//d }

    >>In Perl that is usually written as:
    >>
    >> tr/-//d for values %permutation_map;

    >
    > Nifty. Another Perl right to left pipeline.


    Not a pipeline, a for loop just like:

    for ( values %permutation_map ) { tr/-//d }

    but using the for statement modifier. A pipeline would imply something on the
    left to collect the modified values:

    @permutation_map{ keys %permutation_map } = map { tr/-//d; $_ } values
    %permutation_map;

    BTW, because hash keys cannot be modified, you could (but probably shouldn't)
    write it like this:

    tr/-//d for %permutation_map;

    >>> print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a} <=> $#{$b}} @cycles ), "\n";

    >>Unless you have changed the value of the $" variable you could write that as:
    >>
    >> print join( ' ', map "(@$_)", sort { @$a <=> @$b } @cycles ), "\n";
    >>
    >>Or, to extend that to the next level: :)
    >>
    >> print "@{[ map "(@$_)", sort { @$a <=> @$b } @cycles ]}\n";

    >
    > So what is with the square brackets?
    > Capture the list with a reference,
    > then dereference in the print statement to interpolate $".
    > Yes?


    perldoc perlref
    [snip]
    Here's a trick for interpolating a subroutine call into a string:

    print "My sub returned @{[mysub(1,2,3)]} that time.\n";

    The way it works is that when the "@{...}" is seen in the double-quoted
    string, it's evaluated as a block. The block creates a reference to an
    anonymous array containing the results of the call to "mysub(1,2,3)".
    So the whole block returns a reference to an array, which is then
    dereferenced by "@{...}" and stuck into the double-quoted string. This
    chicanery is also useful for arbitrary expressions:

    print "That yields @{[$n + 5]} widgets\n";

    > I also see the
    >
    > print "@{[ map qq[(@$_)], sort { @$a <=> @$b } @cycles ]}\n";
    >
    > from your follow up article. Elegant.
    >
    > Looking at other folks exemplary code is valuable.
    > Seeing changes to code that I worked over is liberating.


    Those are just suggestions. Benchmark/profile to determine efficiency of any
    code. :)


    John
    --
    use Perl;
    program
    fulfillment
     
    John W. Krahn, Mar 24, 2006
    #5
  6. Michael Press

    Anno Siegel Guest

    Michael Press <> wrote in comp.lang.perl.misc:
    > Thank you all for the help. Would you guys look at
    > the rest of the code? First a disclaimer.
    > The sort assumes numerical permutation elements.
    > This is a limitation I can rectify.
    >
    > ________________CUT________________
    > #! /usr/bin/perl
    >
    > use warnings;
    > use strict;
    >
    > # Multiply permutation cycles, into a permutation map;
    > # then turn the map into a cycle representation, and print.
    > # Knuth ACP 1.3.3 Algorithm B.
    >
    > sub permutation_multiply
    > {
    > my $t;
    > my $hold;
    > my $prev;
    >
    > # Read in the cycles, and initialize the permutation array.
    > my %permutation_map = map { /\w/ ? ( $_ => $_ ) : () } my
    > @token_list = $_[0] =~ /\w+|[()]/g;
    >
    > # Multiply the cycles generating the permutation as a map.
    > for (my $idx = $#token_list; $idx >= 0; --$idx)
    > {
    > my $it = $token_list[$idx];
    > if ($it eq ')' ) { $prev = $it }
    > elsif ($it eq '(' ) { $permutation_map{$hold} = $prev }
    > else
    > {
    > if ( $prev eq ')' ) { $hold = $it }
    > $t = $prev, $prev = $permutation_map{$it},
    > $permutation_map{$it} = $t;
    > }
    > }
    >
    > # Generate the cycle representation from the permutation in
    > %permutation_map
    > my @cycles;
    > for my $key (sort { $a <=> $b } keys %permutation_map)
    > {
    > my @element_list;
    > next if $permutation_map{$key} =~ m/-$/ ;
    > do
    > {
    > push @element_list, $key;
    > $t = $permutation_map{$key};
    > $permutation_map{$key} .= '-';
    > $key = $t;
    > } while ($permutation_map{$key} !~ m/-$/ );
    > push @cycles, [@element_list];
    > }
    > for my $key (keys %permutation_map) {$permutation_map{$key} =~ tr/-//d }
    >
    > # Print out the cycles:
    > # Sort the cycles by length.
    > # Put spaces between permutation elements.
    > # Put in cycle delimiter parentheses.
    > # Put spaces between permutation cycles.
    > # Print.
    > print join(' ', map { sprintf "(%s)", join ' ', @{$_}} sort {$#{$a}
    > <=> $#{$b}} @cycles ), "\n";
    > }
    >
    > my $alpha = "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)";
    > my $beta = "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22
    > 21 19)";
    > my $gamma = "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)(10
    > 16)(12 21)(14 18)";
    > my $delta = "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11
    > 19 22 14 17)";
    > my $x;


    What are all the single-element cycles for? They map to the unit
    permutation and have no effect.

    > print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma alpha^18 \n";
    > $x = ($alpha x 5 . $gamma) x 2 . $alpha x 14 . $gamma . $alpha x 18;
    > permutation_multiply $x;
    > $x = $beta;
    > permutation_multiply $x;
    > print "\n";
    >
    > print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    > $x = (($alpha x 13) . $gamma . ($delta x 2)) x 3;
    > permutation_multiply $x;
    > print "\n";
    >
    > ________________END________________


    One of my projects in the almost-done limbo is a permutation class. It
    overloads permutation objects so that multiplication (x) and exponentiation
    (**) can be applied directly. I had an hour of fun adapting it to the
    problem at hand. The adaption is mainly in the stringification of
    permutations and in the addition of a special creator (new_from_cyc_str)
    to deal with the given formats.

    The code (incompletely tested) is appended below. The printed results
    are equivalent to those of the original code.

    Anno


    #!/usr/bin/perl
    use strict; use warnings; $| = 1;

    my $alpha = Permutation->new_from_cyc_str(
    "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)"
    );

    my $beta = Permutation->new_from_cyc_str(
    "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22 21 19)"
    );

    my $gamma = Permutation->new_from_cyc_str(
    "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)" .
    "(10 16)(12 21)(14 18)"
    );

    my $delta = Permutation->new_from_cyc_str(
    "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11 19 22 14 17)"
    );

    my $x = ($alpha**5 x $gamma)**2 x $alpha**14 x $gamma x $alpha ** 18;

    print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma alpha^18\n";
    print "$x\n";
    print "$beta\n";

    print "\n";
    print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    $x = ($alpha**13 x $gamma x $delta**2)**3;
    print "$x\n";

    exit;

    ######################################################################

    package Permutation;
    use List::Util qw( max);

    use overload(
    # '""' => sub { "(@{ shift() })" },
    '""' => 'to_cyc_str',
    bool => sub { @{ $_[ 0]} > 1 },
    x => 'multiply',
    '/' => 'divide',
    '**' => 'power',
    );

    sub new {
    my $class = shift;
    push @_, 0 unless @_;
    defined $_[ $_] or $_[ $_] = $_ for 0 .. $#_;
    pop while @_ > 1 and $_[ -1] == $#_;
    bless [ @_], $class;
    }

    sub new_from_cycle {
    my $class = shift;
    my @p;
    my @q = @_;
    push @q, shift @q;
    @p[ @_] = @q;
    $class->new( @p);
    }

    sub new_from_cyc_str {
    my ( $class, $str) = @_;
    my $p = $class->new();
    for ( $str =~ /\(([\d ]*)\)/g ) {
    $p = $p->multiply( Permutation->new_from_cycle( split));
    }
    $p;
    }

    sub new_random {
    my ( $class, $n) = @_;
    my @perm = 0 .. $n - 1;
    for ( reverse 0 .. $n - 1 ) {
    my $pick = rand $_;
    @perm[ -1, $pick] = @perm[ $pick, -1];
    }
    $class->new( @perm);
    }

    sub multiply {
    my ( $p1, $p2) = @_;
    ref( $p1)->new( (@$p2, @$p2 .. max( @$p1))[ @$p1, @$p1 .. $#$p2]);
    }

    sub invert {
    my $p = shift;
    my @inv;
    @inv[ @$p] = 0 .. $#$p;
    ref( $p)->new( @inv);
    }

    sub divide { $_[ 0]->multiply( $_[ 1]->invert) }

    sub power {
    my ( $p, $n) = @_;
    if ( $n < 0 ) {
    $n = -$n;
    $p = $p->invert;
    }
    my $pow = Permutation->new();
    while ( $n ) {
    $pow = $pow->multiply( $p) if $n & 1;
    $p = $p->multiply( $p);
    $n >>= 1;
    }
    $pow;
    }

    sub _extract_cycle {
    my $p = shift;
    my ( @seen, @cyc);
    my $i = $#$p;
    until ( defined $seen[ $i] ) {
    $seen[ $i] = 1;
    push @cyc, $i;
    $i = $p->[ $i];
    }
    @cyc;
    }

    sub to_cycles {
    my $p = shift;
    my @cycles;
    while ( $p ) {
    my @cyc = $p->_extract_cycle;
    $p = $p->multiply( Permutation->new_from_cycle( @cyc)->invert);
    push @cycles, \ @cyc;
    }
    sort { @$a <=> @$b } @cycles;
    }

    sub to_cyc_str {
    my $p = shift;
    join ' ', map "[@$_]", $p->to_cycles;
    }
    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Mar 24, 2006
    #6
  7. In article <>,
    -berlin.de (Anno Siegel) wrote:

    > Michael Press <> wrote in comp.lang.perl.misc:


    [...]

    > > my $alpha = "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)";
    > > my $beta = "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22
    > > 21 19)";
    > > my $gamma = "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)(10
    > > 16)(12 21)(14 18)";
    > > my $delta = "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11
    > > 19 22 14 17)";
    > > my $x;

    >
    > What are all the single-element cycles for? They map to the unit
    > permutation and have no effect.


    These are (redundant) generators of a real world group. As
    you see in the next bit of code, if the singletons were
    not present in $beta, then the result of
    permutation_multiply $beta and
    permutation_multiply ($alpha x 2 ...
    would not be the same.

    But more importantly these are generators of
    PSL_2 (GF_23), the group of automorphisms over the
    projective line in GF_23. GF_23 has 23 elements:
    {0, 1, ... 23}. The projective line has 24 elements:
    {infinity, 0, 1, ... 23}. (I use 99 for infinity).

    Since the permutation beta is an automorphism, we must
    define its behavior on every point. The fixed points of
    group elements are important in the analysis, so it is
    better when reading to see the singletons explicitly,
    rather than trying to infer them. For instance
    (alpha delta)^3 = (0) (1) (5) (6) (18) (20) (22) (99)
    (2 3) (4 15) (7 8) (9 11) (10 19) (12 16) (13 21) (14 17)

    The group is the Mathieu group M_24.
    It is generated by alpha and (gamma delta^2).

    The automorphisms have algebraic expressions:
    z alpha = z + 1
    z beta = 2z
    z gamma = -1/z
    delta is a bit more complicated.

    Here are more relations:
    print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma
    alpha^18 \n";
    print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    print "delta alpha^2 is 1^3 7^3 \n";
    print "(alpha delta)^3 has shape 1^8 2^8\n";
    print "gamma delta^2 \n";
    print "(gamma delta^2)^5 = gamma \n";
    print "(gamma delta^2)^8 = delta \n";
    print "beta gamma delta^2 = gamma delta^2 beta^2 \n";
    print "alpha^5 delta has shape 1^2 2^1 4^1 8^2\n";
    print "delta alpha^11 has shape 1^1 3^1 5^1 15^1\n";
    print "(delta alpha^11)^5 has shape 1^6 3^6\n";


    > > print "beta = alpha^5 gamma alpha^5 gamma alpha^14 gamma alpha^18 \n";
    > > $x = ($alpha x 5 . $gamma) x 2 . $alpha x 14 . $gamma . $alpha x 18;
    > > permutation_multiply $x;
    > > $x = $beta;
    > > permutation_multiply $x;
    > > print "\n";
    > >
    > > print "(alpha^13 gamma delta^2)^3 has shape 4^6\n";
    > > $x = (($alpha x 13) . $gamma . ($delta x 2)) x 3;
    > > permutation_multiply $x;
    > > print "\n";
    > >
    > > ________________END________________

    >
    > One of my projects in the almost-done limbo is a permutation class. It
    > overloads permutation objects so that multiplication (x) and exponentiation
    > (**) can be applied directly. I had an hour of fun adapting it to the
    > problem at hand. The adaption is mainly in the stringification of
    > permutations and in the addition of a special creator (new_from_cyc_str)
    > to deal with the given formats.
    >
    > The code (incompletely tested) is appended below. The printed results
    > are equivalent to those of the original code.


    Well, it will take me a bit of study. :)

    --
    Michael Press
     
    Michael Press, Mar 24, 2006
    #7
  8. Michael Press

    Anno Siegel Guest

    Michael Press <> wrote in comp.lang.perl.misc:
    > In article <>,
    > -berlin.de (Anno Siegel) wrote:
    >
    > > Michael Press <> wrote in comp.lang.perl.misc:

    >
    > [...]
    >
    > > > my $alpha = "(99)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

    > 20 21 22)";
    > > > my $beta = "(99)(0)(3 6 12 1 2 4 8 16 9 18 13)(15 7 14 5 10 20 17 11 22
    > > > 21 19)";
    > > > my $gamma = "(99 0)(1 22)(2 11)(3 15)(4 17)(5 9)(6 19)(7 13)(8 20)(10
    > > > 16)(12 21)(14 18)";
    > > > my $delta = "(99)(0)(3)(15)(1 18 4 2 6)(5 21 20 10 7)(8 16 13 9 12)(11
    > > > 19 22 14 17)";
    > > > my $x;

    > >
    > > What are all the single-element cycles for? They map to the unit
    > > permutation and have no effect.

    >
    > These are (redundant) generators of a real world group. As
    > you see in the next bit of code, if the singletons were
    > not present in $beta, then the result of
    > permutation_multiply $beta and
    > permutation_multiply ($alpha x 2 ...
    > would not be the same.


    Hmm... Well, permutation_multiply() does more than its name implies
    (printing out results on its own). Otherwise, the result of a permutation
    multiplication should be independent of (redundant) singleton cycles
    in the specification of the factors.

    You appear to use the singletons as some kind of marker. I haven't seen
    that technique before, and computationally it strikes me as cumbersome.
    I'd try to make those markers independent of the basic permutation
    operations.

    > But more importantly these are generators of
    > PSL_2 (GF_23), the group of automorphisms over the
    > projective line in GF_23. GF_23 has 23 elements:
    > {0, 1, ... 23}. The projective line has 24 elements:
    > {infinity, 0, 1, ... 23}. (I use 99 for infinity).
    >
    > Since the permutation beta is an automorphism, we must
    > define its behavior on every point.


    Huh? If it were only an endomorphism we wouldn't have to define
    its behavior in every point? I don't understand that argument.

    > The fixed points of
    > group elements are important in the analysis, so it is
    > better when reading to see the singletons explicitly,
    > rather than trying to infer them. For instance
    > (alpha delta)^3 = (0) (1) (5) (6) (18) (20) (22) (99)
    > (2 3) (4 15) (7 8) (9 11) (10 19) (12 16) (13 21) (14 17)


    The fixed points of a permutation are exactly the elements that
    don't appear in a cycle of length > 1. Computationally that's
    very simple (once you have the non-singleton cycles).

    [too much group theory for a Saturday afternoon snipped]

    Anno
    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Mar 25, 2006
    #8
  9. In article <>,
    -berlin.de (Anno Siegel) wrote:

    > Michael Press <> wrote in comp.lang.perl.misc:
    > > In article <>,
    > > -berlin.de (Anno Siegel) wrote:
    > > > What are all the single-element cycles for? They map to the unit
    > > > permutation and have no effect.

    > >
    > > These are (redundant) generators of a real world group. As
    > > you see in the next bit of code, if the singletons were
    > > not present in $beta, then the result of
    > > permutation_multiply $beta and
    > > permutation_multiply ($alpha x 2 ...
    > > would not be the same.

    >
    > Hmm... Well, permutation_multiply() does more than its name implies
    > (printing out results on its own). Otherwise, the result of a permutation
    > multiplication should be independent of (redundant) singleton cycles
    > in the specification of the factors.


    Yes, it should be factored out. I wrote the code as an
    adjunct to some reading.

    > You appear to use the singletons as some kind of marker.


    No, not a marker. They are parts of the definitions of
    their respective automorphisms.

    > I haven't seen
    > that technique before, and computationally it strikes me as cumbersome.
    > I'd try to make those markers independent of the basic permutation
    > operations.


    I do not follow this. I want to _see_ the fixed points
    when I print out the permutation. Why do you want to
    delete them for me?

    Cumbersome is not knowing the domain of the permutation.

    > > But more importantly these are generators of
    > > PSL_2 (GF_23), the group of automorphisms over the
    > > projective line in GF_23. GF_23 has 23 elements:
    > > {0, 1, ... 23}. The projective line has 24 elements:
    > > {infinity, 0, 1, ... 23}. (I use 99 for infinity).
    > >
    > > Since the permutation beta is an automorphism, we must
    > > define its behavior on every point.

    >
    > Huh? If it were only an endomorphism we wouldn't have to define
    > its behavior in every point? I don't understand that argument.


    I am not interested in these permutations as
    endomorphisms. They are interesting as automorphisms.
    An endomorphism B need not satisfy B(xy)= B(x)B(y). An
    automorphism must be defined at each element of the
    domain.

    > > group elements are important in the analysis, so it is
    > > better when reading to see the singletons explicitly,
    > > rather than trying to infer them. For instance
    > > (alpha delta)^3 = (0) (1) (5) (6) (18) (20) (22) (99)
    > > (2 3) (4 15) (7 8) (9 11) (10 19) (12 16) (13 21) (14 17)

    >
    > The fixed points of a permutation are exactly the elements that
    > don't appear in a cycle of length > 1. Computationally that's
    > very simple (once you have the non-singleton cycles).


    If I delete one-cycles, then I must carry around the
    domain of the permutations in my head. I have better uses
    for that space. If I know that the permutation explicitly
    defines the transformation, than I know the domain. In
    these investigations more than one set of elements and
    their permutation groups are considered at the same time.

    Computers were invented to carry out tedious calculations.

    --
    Michael Press
     
    Michael Press, Mar 30, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger B.
    Replies:
    13
    Views:
    616
    D.F.S.
    Sep 26, 2003
  2. fadliwdt

    [help] String permutation with input

    fadliwdt, Nov 17, 2006, in forum: C Programming
    Replies:
    0
    Views:
    436
    fadliwdt
    Nov 17, 2006
  3. permutation code.

    , Jul 9, 2006, in forum: C Programming
    Replies:
    4
    Views:
    371
    osmium
    Jul 9, 2006
  4. Haoqi Haoqi
    Replies:
    3
    Views:
    122
    Paul Smith
    Nov 13, 2009
  5. Robert Hayes

    variable length permutation code

    Robert Hayes, Jan 28, 2012, in forum: C Programming
    Replies:
    5
    Views:
    690
    Peter Nilsson
    Jan 31, 2012
Loading...

Share This Page