usingMaths.com
From Theory to Practice - Math You Can Use.







<< PreviousNext >>

Code for Permutation (Possible Ways of Arrangement) in Perl



Permutation - What It Is.

In the unlikely scenario that the Teacher wanted to see just how any four pupils, in a class of six (6), could be seated on a four-person desk; what this Teacher would be doing in essence is called Permutation (nPr).



Code for Doing Permutation in Perl

The algorithm for Permutation - nPr, possible ways of arrangement - will simply be based on that of combination.

All that is needed after combination is a rotation / shuffle of the make-up / constituents of each possible combination result.

This shuffle simply involves interchanging the elements of the combination group of size, r, to take all possible positions starting from the extreme right to extreme left.

This is how our Permutation code in Perl will work.

Create a new Perl module file;
Call it Permutation.pm
Type out the adjoining Perl code for Permutation (nPr).



Advice: You might want to keep the mother-class size (n) and the group-size (r) small to avoid the permutation code taking too long.
As a rule-of-thump, DO NOT ASK QUESTIONS YOU DON'T WANT TO KNOW THE ANSWER TO.







Perl Code for Permutation.pm Module

package PERMUTATION;

BEGIN {
    require Exporter;

    # for the sake of standard
    our $VERSION = 2017.10;

    # Inherit from exporter to export subs and variables
    our @ISA = qw(Exporter);

    # subs and variables to be exported by default
    our @EXPORT_OK = qw(possibleWordPermutations);
}

use 5.010;
use warnings;
use strict;

our @words;
our $r; # min length of word
my @local_store; # array of references
my @perm_store; # array of references
my $eye;
my $combination;

# simulate an object construct
sub new {
    my $self = shift;
    
    my $this = {};
    bless $this, $self;
    
    return $this;
}

# till the ground for shuffle to grind on
# returns an array reference of references to array strings
sub possibleWordPermutations {
    shift;
    my $arg = shift;
    @words = @{$arg};
    $r = shift;
    @perm_store = ();
    
    use COMBINATION;
    my $call = COMBINATION->new();
    # $combination receives an array reference of references
    $combination = $call->possibleWordCombinations(\@words, $r);
    
    # illegal 'r' value
    if (!defined $combination->[0] || $r == 1) {
        @perm_store = @{$combination};
    } else {
        
        for (0 .. $#{$combination}) {
            $eye = $r - 1;
            # copy up last two elements of 'comb_store.get(i)'
            my @last_two = (["", ""], ["", ""]); # array of references
            $last_two[0]->[0] = $last_two[1]->[1] = $combination->[$_]->[$eye--];
            $last_two[0]->[1] = $last_two[1]->[0] = $combination->[$_]->[$eye--];
            
            @local_store = (); # array of references
            push @local_store, $last_two[0], $last_two[1];
            shuffleWord([@local_store], $_) if $r > 2;

            push @perm_store, @local_store;
        }
    }
    return \@perm_store;
}

sub shuffleWord {
    my $arg_store = shift; # array reference of references
    my $i = shift;
    @local_store = ();
    my @members;
    for my $entry (@{$arg_store}) {
        @members = @{$entry};
        # add 'comb_store[i][eye]' element to this list of members
        push @members, $combination->[$i]->[$eye];

        my $shift_index = scalar @members;
        # shuffle this pack of words
        while ($shift_index > 0) {
            # skip if already in store -- /* array comparism */
            my ($contains) = grep { @{$local_store[$_]} ~~ @members } 0 .. $#local_store;
            if (!defined $contains) {
                push @local_store, [@members];
            }
            # interchange these two neighbours
            if (--$shift_index > 0 && $members[$shift_index] ne $members[$shift_index - 1]) {
                @members[$shift_index - 1, $shift_index] = @members[$shift_index, $shift_index - 1];
            }
        }
    }
    # Are there any elements left? repeat if yes
    if ($eye-- > 0) {
        shuffleWord([@local_store], $i);
    }
}

1;

Main Class

#!/usr/bin/perl;

use strict;
use warnings;

use PERMUTATION;

my @subjects = ("Eno", "Chidi", "Olu", "Ahmed", "Osas", "Gbeda");
my $r = 4;

# Use the permutation module/class
my $perm = PERMUTATION->new();

# $result receives an array reference of references
my $result = $perm->possibleWordPermutations(\@subjects, $r);

print ("[", join(", ", @subjects), "] permutation ", $r, ":\n\n");
# for each array reference in a dereferenced '$result'
my $i = 0;
print (++$i, ": ", join(", ", @{$_}), "\n") for @{$result};
print ("\n\nNumber of ways is ", scalar @{$result}, ".");

print "\n\n";



<< PreviousNext >>