Find all permutations of a string in C++

Question

I need a review of the following code for finding all permutations of a string in C++:

List Permute(const String& string)
{
 if (string.length == 0)
 return EmptyStrings(1);
 List prevList = Permute(SubString(string,1,string.length));
 List nextList = EmptyStrings(string.length*prevList.length);
 for (int i=0; i<prevList.length; i++)
 {
 for (int j=0; j<string.length; j++)
 {
 nextList[i*string.length+j] += SubString(prevList[i],0,j);
 nextList[i*string.length+j] += string[0];
 nextList[i*string.length+j] += SubString(prevList[i],j,string.length-1);
 }
 }
 return nextList;
}

You may assume the correctness of the following:

class List
class String
List EmptyStrings(int n); // returns a list of 'n' empty strings
String SubString(const String& string,int i,int j); // returns the string 'string[i...j)'

• red_eight: This is cheating, but I thought it would be nice to mention that <algorithm> has useful functions for this such as next_permutation, prev_permutation, and is_permutation.

Answer 1

You may need to remove duplicates. Consider what your output will be if, for example, your input string is "aaa".

---

Code like this is unusual:

// nextList contains an array of empty strings
nextList[i*string.length+j] += SubString(prevList[i],0,j);

IMO this would be more usual:

// nextList is empty
// calculate new string
string nextString = SubString(prevList[i],0,j)
 + string[0]
 + SubString(prevList[i],j,string.length-1);
nextList.Add(nextString);

---

Returning by value is sometimes necessary but can be inefficient. Your algorithm creates many temporary List objects. A better API might be ...

void Permute(const String& inputString, List& outputList) { ... }

... where one empty List is allocated by the caller, and you add to it.

---

This statement may be incorrect ...

List prevList = Permute(SubString(string,1,string.length));

... I don't know how returns the string 'string[i...j)' is defined but perhaps this statement should be ...

List prevList = Permute(SubString(string,1,string.length - 1));

---

You may run out of memory very quickly. For a string of length n there are n! ('n factorial') permutations. "what's up doc?" has 14 characters => 87178291200 (or 0x144C3B2800) i.e. bigger than 2³² combinations.

• barak manos: Never thought of the possibility of duplicates, thanks
• barak manos: As to the 'run out of memory' - that will obviously happen regardless of how efficient my method is in terms of memory consumption, due to the number of permutations itself
• ChrisW: It's true that Combinatorial optimization is a non-trivial problem for computer scientists. Perhaps (I don't know) if you search you'll find (previously researched) algorithms for this "permutations of a string" problem. IMO there might be a solution which can work for larger strings, by generating/outputing the list of permutations to a (larger than 4 GB) output file on disk.
• Loki Astari: Returning by value is unlikely to inefficient. RVO and NRVO basically prevent the copy from happening (ie it is elided). So prefer to use the more natural style of return by value. Also with move semantics in C++11 it becomes important to use return by value so that these kick in as expected automatically.