×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Jobs

Data manipulation

How to generate a list of permutations of a set of symbols by prex1
Posted: 8 Oct 07 (Edited 2 Mar 08)

It is known that the number of different permutations of n symbols using all n symbols is P(n,n)=n!, see Permutation - Wikipedia.
To generate a list of all the permutations use the template function below. The sub permutations returns, by using recursion, a reference to an array containing a list of strings composed of the characters chr(0) to chr(n-1), each string representing a permutation of the numbers (0..n-1), that may be used as indices into the set of symbols as shown below in the code.
Be prepared to be patient if n>12 and, if n>20, you could have to wait for the next big bang starting a new universe expansion before you get the result!

CODE

use strict;
use warnings;
my@symbols=('a','b','c','d');
my$start=join'',map{chr}(0..$#symbols);
my$refallperms=permutations(\$start);
for my$p(@{$refallperms}){
  for my$q(0..$#symbols){
    print$symbols[ord(substr($p,$q))],' ';
  }
  print"\n";
}
print'Number of permutations of ',$#symbols+1," symbols: ",scalar@{$refallperms},"\n";
#####################################################
sub permutations{
  my($refin)=@_;
    #reference to a string containing n different chr's
  return[$$refin]if length($$refin)==1;
  local($_);
  my(@perm,$i,$s);
  my$news=substr($$refin,-1);
  for(@{permutations(\substr($$refin,0,-1))}){
    for($i=0;$i<length$$refin;$i++){
      $s=$_;
      substr($s,$i,0,$news);
      push@perm,$s;
    }
  }
  return\@perm;
}
The permutations of n symbols in groups of r are P(n,r)=n!/(n-r)!. Calculating these is harder. The code below presents a solution where the combinations (=unordered permutations) are first calculated, then for each one of them all the permutations of the contained symbols are found.

CODE

use strict;
use warnings;
my@symbols=('a','b','c','d','e');
my$grouping=3;
die"You can't group ",$#symbols+1," symbols $grouping by $grouping!\n"if$grouping>$#symbols;
my$refallperms=permutations_nxr($#symbols,$grouping-1);
for my$p(@$refallperms){
  for my$q(0..$grouping-1){
    print$symbols[ord(substr($p,$q))],' ';
  }
  print"\n";
}
print'Number of permutations of ',$#symbols+1," symbols $grouping by $grouping: ",scalar@{$refallperms},"\n";
#####################################################
sub permutations_nxr{
  my($n,$r)=@_;
  my$refperm=combinations($n,$r);
  my@perms;
  for(@$refperm){
    push@perms,@{permutations(\$_)};
  }
  return\@perms;
}
#####################################################
sub combinations{
  my($n,$r)=@_;
  my(@comb,@newc,$i,$j,$c);
  local($_);
  @comb=map{chr}(0..$n-$r);
  for($i=$n-$r+1;$i<=$n;$i++){
    for(@comb){
      $j=1+ord(substr($_,-1));
      last if$j>$i;
      $c=$_;
      $_.=chr($j);
      for($j++;$j<=$i;$j++){
        push@newc,$c.chr($j);
      }
    }
    push@comb,@newc;
    @newc=();
  }
  return\@comb;
}
#####################################################
sub permutations{
  my($refin)=@_;
    #reference to a string containing n different chr's
  return[$$refin]if length($$refin)==1;
  local($_);
  my(@perm,$i,$s);
  my$news=substr($$refin,-1);
  for(@{permutations(\substr($$refin,0,-1))}){
    for($i=0;$i<length$$refin;$i++){
      $s=$_;
      substr($s,$i,0,$news);
      push@perm,$s;
    }
  }
  return\@perm;
}

Back to Perl FAQ Index
Back to Perl Forum

My Archive

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close