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

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

gevni
Novice

Nov 23, 2012, 4:33 AM

Post #1 of 3 (3061 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 (3057 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 (3049 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

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0