More help requested on permutation code.

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
.

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: More help requested on permutation code.
    ... The sort assumes numerical permutation elements. ... # Read in the cycles, ... In Perl that is usually written as: ...
    (comp.lang.perl.misc)
  • 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)