Recursive permutations

A while ago I was looking for a method to compute permutations of a string of n elements taken from a set of k symbols. After many very complicated tries, I came to a very simple method using a recursive function. It is given hereafter in Javascript:

function calc(n, symbols, str)
{
  if(!str)
    str = ""
  if(str.length==n)
    perms.push(str);
  else
    for(var i=0;i<symbols.length;i++)
      calc(n, symbols.substr(0,i) + symbols.substr(i+1,100), str + symbols.charAt(i));
}

The variable perms is a global array. The function works with elements placed in a character string. It uses 3 parameters: n is the size of the output string, symbols is a character string containing the symbols in lexical order, str is a temporary string used for the recursion and should not be set for a normal call.

As an example, the call calc(3, "ABCD") will produce the following values in perms:

ABC, ABD, ACB, ACD, ADB, ADC,
BAC, BAD, BCA, BCD, BDA, BDC,
CAB, CAD, CBA, CBD, CDA, CDB,
DAB, DAC, DBA, DBC, DCA, DCB

This is certainly not the most optimized algorithm to compute permutations (other methods exist), but it is so simple that I wanted to share it.

Advertisements

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: