Re: More help requested on permutation code.

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
.

Relevant Pages

  • Re: VMPC Stream Cipher - ideas on potential weaknesses?
    ... > terabytes of bytes and digraphs through our ... It would be interesting to know about the possible short cycles. ... My geuss is that the algorithm mixes the permutation well enough to avoid ...
    (sci.crypt)
  • Re: More help requested on permutation code.
    ... The sort assumes numerical permutation elements. ... sub permutation_multiply ... # Read in the cycles, ... my $class = shift; ...
    (comp.lang.perl.misc)
  • Re: ANNOUNCE: New "Leopard6" CSPRNG !
    ... and it always reports s]. ... also a permutation of 0..255. ... same set of cycles, except any cycles of even length in the internal ... Voila, the internal state. ...
    (sci.crypt)
  • Re: Permutation of maximum cycle
    ... assume you have a permutation of maximal period k=k. ... Wlog assume that p was chosen among all permutations of maximal order ... Consider any two such distinct cycles of periods k1, ...
    (sci.math)
  • More help requested on permutation code.
    ... The sort assumes numerical permutation elements. ... # Read in the cycles, ...
    (comp.lang.perl.misc)