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

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

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

 



gevni
Novice

Nov 23, 2012, 4:33 AM

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

Hi
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



Code
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;
for($j=0;$j<$card;$j++){
@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;
last;
}
}
&$func($j) if defined $res;
}
return 0;
}


Plz let me know how I can modify it?


Laurent_R
Veteran / Moderator

Nov 23, 2012, 10:06 AM

Post #2 of 3 (1473 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.


BillKSmith
Veteran

Nov 23, 2012, 5:43 PM

Post #3 of 3 (1465 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,
Bill

 
 


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

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