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)'

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.