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