Velocity Reviews > Perl > More help requested on permutation code.

# More help requested on permutation code.

Michael Press
Guest
Posts: n/a

 03-24-2006
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 1";
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

John W. Krahn
Guest
Posts: n/a

 03-24-2006
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 1";
> 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
Guest
Posts: n/a

 03-24-2006
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

Michael Press
Guest
Posts: n/a

 03-24-2006
In article <aHLUf.1707\$B_1.825@edtnps89>,
"John W. Krahn" <(E-Mail Removed)> 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";

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

--
Michael Press

John W. Krahn
Guest
Posts: n/a

 03-24-2006
Michael Press wrote:
> In article <aHLUf.1707\$B_1.825@edtnps89>,
> "John W. Krahn" <(E-Mail Removed)> 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";
>
>
> 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

Anno Siegel
Guest
Posts: n/a

 03-24-2006
Michael Press <(E-Mail Removed)> 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 1";
> 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 1"
);

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);

# '""' => 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

Michael Press
Guest
Posts: n/a

 03-24-2006
In article <(E-Mail Removed)>,
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Anno Siegel) wrote:

> Michael Press <(E-Mail Removed)> 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 1";
> > 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) (1 (20) (22) (99)
(2 3) (4 15) (7 (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

Anno Siegel
Guest
Posts: n/a

 03-25-2006
Michael Press <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> In article <(E-Mail Removed)>,
> (E-Mail Removed)-berlin.de (Anno Siegel) wrote:
>
> > Michael Press <(E-Mail Removed)> 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 1";
> > > 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) (1 (20) (22) (99)
> (2 3) (4 15) (7 (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

Michael Press
Guest
Posts: n/a

 03-30-2006
In article <(E-Mail Removed)>,
(E-Mail Removed)-berlin.de (Anno Siegel) wrote:

> Michael Press <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> > In article <(E-Mail Removed)>,
> > (E-Mail Removed)-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

> 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) (1 (20) (22) (99)
> > (2 3) (4 15) (7 (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