×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
• Talk With Other Members
• Be Notified Of Responses
• Keyword Search
Favorite Forums
• Automated Signatures
• Best Of All, It's Free!

*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.

# Perl FAQ

## 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'); mygrouping=3; die"You can't group ",#symbols+1," symbols grouping by grouping!\n"ifgrouping>#symbols; myrefallperms=permutations_nxr(#symbols,grouping-1); for myp(@refallperms){ for myq(0..grouping-1){ printsymbols[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)=@_; myrefperm=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 ifj>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); mynews=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

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:

• Talk To Other Members
• Notification Of Responses To Questions
• Favorite Forums One Click Access
• Keyword Search Of All Posts, And More...

Register now while it's still free!