Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

How to generate a list of permutations of a set of symbols

Data manipulation

How to generate a list of permutations of a set of symbols

by  prex1  Posted    (Edited  )
It is known that the number of different permutations of n symbols using all n symbols is P(n,n)=n!, see [link http://en.wikipedia.org/wiki/Permutation]Permutation - Wikipedia[/link].
To generate a list of all the permutations use the template function below. The [tt]sub permutations[/tt] 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;
}
Register to add this FAQ to your archive
Register to rate this FAQ  : BAD 1 2 3 4 5 6 7 8 9 10 GOOD
Please Note: 1 is Bad, 10 is Good :-)

Part and Inventory Search

Back
Top