Home: Perl Programming Help: Intermediate:
How to reduce redundant permutations?


Nov 23, 2012, 4:33 AM

Views: 3134
How to reduce redundant permutations?

I have this function that will exclude the redundant permutations. If processes are adjacent and belongs to same group it will exclude this permutation order. I need to change it like it will check all the processes that belongs to same group and skip all these combination weather they are adjacent or not but belongs to the same group For example :
Let we have 4 processes. Total No of permutations are 4!=24

<b> 0 1 2 3 (here 0,1,3 belongs to same group) </b>

This function will exclude the permutation that interchange 0 with 1 and i want to modify it like it will exclude all the permutations order that have same group weather they are adjacent or not like it may exclude 0 with 3 permutation order too . Function is

sub Apply_on_index(&@)  
my $func = shift;
my $array = shift;
my $group = shift;
return undef unless (defined $func and defined $array);
my $rest;
my $i;
my $j;
my @array;
my $size = $#{$array}+1;
my $card = factorial($size);
my $res;
@array = @{$array};
$res = [];
$rest = $j;
$i = 0;
for($i = 0; $i <= $#{$array}; $i++){
${$res}[$i] = splice @array, $rest % ($#array + 1), 1;
$rest = int($rest / ($#array + 2));
if ($i > 0 and ${$res}[$i] < ${$res}[$i-1] and
${$group}[${$res}[$i]] == ${$group}[${$res}[$i-1]]){
$res = undef;
&$func($j) if defined $res;
return 0;

Plz let me know how I can modify it?

Veteran / Moderator

Nov 23, 2012, 10:06 AM

Views: 3130
Re: [gevni] How to reduce redundant permutations?

If the number of elements is small (e.g. 4 in your example), then you might generate all permutations and use a hash to remove those that are duplicates elements of the same group at the same place). This may look like brute force approach, but if you can do it in a couple of code lines, rather than a few dozens, it might be the best approach.


Nov 23, 2012, 5:43 PM

Views: 3122
Re: [gevni] How to reduce redundant permutations?

I am still not clear about your requirements, but it is very likely that there is a module that does what you want. I suggest that you consider CPAN modules that have the word "combinatorics" in their names. Even if you do not find a useful module, the search will probably help you in the use of standard terminology.
Good Luck,