The Labs.Com Issue_11_Permutations

TPJ: Issue_11_Permutations

This is a collection of programs published by The Perl Journal. You can download all source-code also from TPJ: Programs.

Download perm.pl

#!/usr/bin/perl

use strict;

sub permute_init

{

my($digits) = shift;

return([ [[], $digits] ]);

}

sub permute_next

{

my ($state) = shift;

my ($left, $right);

my ($newleft, $newright);

my ($val, $item, $i, $done);

$item = pop(@$state);

if (defined($item)){

($left, $right) = @$item;

while(! $done){

if(scalar(@$right) > 0){

foreach $i (0 .. (scalar(@$right) - 1)\

) {

$newright  = [];

$newleft   = [];

@$newright = @$right;

@$newleft  = @$left;

push(@$newleft,

splice(@$newright, $i,\

1));

unshift(@$state,

[$newleft, $newright])\

;

}

}

if(scalar(@$left) > 0){

$val = join('', @$left);

$done = 1;

}else{

$item = pop(@$state);

($left, $right) = @$item;

}

}

}

return($state, $val);

}

sub main

{

my ($state1, $state2, $val1, $val2);

my ($digits, $result, $count, $tries);

my ($tmp, $diff, $len, $bests, $bestdiff);

$digits = [9, 2, 3, 8, 6];

$result = 5029;

$| = 1;

$tries = 0; $bestdiff = 99999;

$len = scalar(@$digits);

$state1 = &permute_init($digits);

($state1, $val1) = &permute_next($state1);

while(defined($val1)){

$state2 = &permute_init($digits);

($state2, $val2) = &permute_next($state2);

while(defined($val2)){

$tmp = $val1 - $val2 - $result;

if ($tmp < 0){

$tmp = -$tmp;

}

if ($tmp == $bestdiff){

$count++;

push(@$bests, [$val1, $val2]);

}elsif ($tmp < $bestdiff){

$count = 1;

$bests = [[$val1, $val2]];

$bestdiff = $tmp;

}

$tries++;

($state2, $val2) = &permute_next($state2);

}

($state1, $val1) = &permute_next($state1);

}

print("$tries different possibilities were tested.\n");

print("There are $count answers that are off by $bestdiff\n");

foreach $tmp (@$bests){

($val1, $val2) = @$tmp;

printf("%${len}d - %${len}d = %${len}d\n",

$val1, $val2, $val1 - $val2);

}

}

&main

Issue_11_Permutations 2. More Samples on Permutations

• Issue_11_Permutations