More help requested on permutation code.

M

Michael Press

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________________
 
J

John W. Krahn

Michael said:
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 "(@$_)" said:
}

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
 
J

John W. Krahn

John said:
Michael said:
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
 
M

Michael Press

John W. Krahn said:
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?

[...]
In Perl that is usually written as:

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

I knew that. :)

[...]
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.
 
J

John W. Krahn

Michael said:
John W. Krahn said:
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
 
A

Anno Siegel

Michael Press said:
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;
}
 
M

Michael Press

[...]
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";

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. :)
 
A

Anno Siegel

Michael Press said:
[...]
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
 
M

Michael Press

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.
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.
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top