Generating Unique Permutations Programmatically

Download UniquePermutation.zip The numbers of permutations on a set of n elements is n! (see definition). or example permutations of the word “ask” are:

ask, aks, sak, ska, kas, ksa

We often need to obtain unique permutations over a given set programmatically. Take the word “good” for example, the unique permutations are:

good, godo, gdoo, ogod, ogdo, oogd, oodg, odgo, odog, dgoo, dogo, doog

And we can prove mathematically that the total number of the permutations is :

Unique Permutation Calculation

 

where n is the length of the sequence and m is the number of a non-unique letter. In the example given above, n = 4 and i = 1 (only one letter “o” is non-unique and it has two o’s, so m = 2 and 4!/2! = 12. The following is the C# code I wrote to achieve this:

class Program {

public ArrayList Unique(string s) {

char[] c = s.ToCharArray();

ArrayList ayList = new ArrayList();

for (int i = 0; i < c.Length; i++)

if (!ayList.Contains(c[i])) ayList.Add(c[i]);

return ayList;

}

public ArrayList Permute(string s) {

ArrayList tmpList = new ArrayList();

ArrayList permList = new ArrayList();

if (s.Length == 1) {

if (!permList.Contains(s)) permList.Add(s);

return permList;

} else {

ArrayList list = Unique(s);

foreach (char c in list) {

for (int i = 0; i < s.Length; i++) {

string tempS = string.Empty;

if (s.Substring(i, 1) == c.ToString())

tempS = s.Remove(i, 1);

else

continue;

tmpList = Permute(tempS);

foreach (string t in tmpList) {

if (!permList.Contains(c.ToString() + t))

permList.Add(c.ToString() + t);

}

}

}

}

return permList;

}

static void Main(string[] args) {

Program p = new Program();

ArrayList ayList = p.Permute("good");

foreach (string s in ayList) Console.WriteLine(s);

Console.WriteLine();

Console.ReadKey();

}

}

The main routine is the function Permute(string s), it takes a string s and builds an array list of permutated strings recursively. Note the function Unique(string s), which takes a string and returns an array list of the unique characters in that string. The uniqueness of the permutation is guaranteed by the foreach loop over tmpList, where only the unique permutations are added to the permList. The routine works pretty well for sequences lengths up to about eight. And because of the complexity grows exponentially, this algorithm is not suited for finding unique permutations over a large set.

Be Sociable, Share!

Leave a Reply