CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
Search Posts SEARCH
Who's Online WHO'S
Log in LOG

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



Nov 23, 2012, 4:33 AM

Post #1 of 3 (2869 views)
How to reduce redundant permutations? Can't Post

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

Post #2 of 3 (2865 views)
Re: [gevni] How to reduce redundant permutations? [In reply to] Can't Post

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

Post #3 of 3 (2857 views)
Re: [gevni] How to reduce redundant permutations? [In reply to] Can't Post

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,


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives