# Programming Interview Questions 11: All Permutations of String

The title says it all, this is a pretty standard interview question. Generate all permutations of a given string.

This may seem hard at first but it’s in fact pretty easy once we figure out the logic. Let’s say we’re given a string of length N, and we somehow generated some permutations of length N-1. How do we generate all permutations of length N? Demonstrating with a small example will help. Let the string be ‘LSE’, and we have length 2 permutations ‘SE’ and ‘ES’. How do we incorporate the letter L into these permutations? We just insert it into every possible location in both strings: beginning, middle, and the end. So for ‘SE’ the result is: ‘LSE’, ‘SLE’, ‘SEL’. And for the string ‘ES’ the results is: ‘LES’, ‘ELS’, ‘ESL’. We inserted the character L to every possible location in all the strings. This is it!. We will just use a recursive algorithm and we’re done. Recurse until the string is of length 1 by repeatedly removing the first character, this is the base case and the result is the string itself (the permutation of a string with length 1 is itself). Then apply the above algorithm, at each step insert the character you removed to every possible location in the recursion results and return. Here is the code:

```def permutations(word): if len(word)&lt;=1: return [word]   #get all permutations of length N-1 perms=permutations(word[1:]) char=word[0] result=[] #iterate over all permutations of length N-1 for perm in perms: #insert the character into every possible location for i in range(len(perm)+1): result.append(perm[:i] + char + perm[i:]) return result```

We remove the first character and recurse to get all permutations of length N-1, then we insert that first character into N-1 length strings and obtain all permutations of length N . The complexity is O(N!) because there are N! possible permutations of a string with length N, so it’s optimal. I wouldn’t recommend executing it for strings longer than 10-12 characters though, it’ll take a long time. Not because it’s inefficient, but inherently there are just too many permutations.

This is one of the most common interview questions, so very useful to know by heart.

VN:F [1.9.22_1171]
Programming Interview Questions 11: All Permutations of String, 8.3 out of 10 based on 35 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• ANONYMOUS

another similar good question, get all generated sub strings of a string.
for xyz, the result is : x, y, z, xy, xz, yz, xyz.
but xy, yx are considered one result.

• Arden

This certainly is a great question, all combinations of a string. I can write about this one as well. Thanks for the suggestion.

• Anonymous

It seems to be sub sequence not sub string.

This is the function I wrote in JS to do the same thing. Can you consider if you use it for your next write-up?

• crazy

can you write this logic in c# or c language.. while(i–) does not works in c# since it is expecting a bool..

• Paul Sweeney Jr

while(i– > 0)

• Yang

Here is an equal java implementation:
``` public static void permuteString(String beginningString, String endingString) { if (endingString.length() <= 1) System.out.println(beginningString + endingString); else for (int i = 0; i < endingString.length(); i++) { try { String newString = endingString.substring(0, i) + endingString.substring(i + 1);```

``` ```

``` permuteString(beginningString + endingString.charAt(i), newString); } catch (StringIndexOutOfBoundsException exception) { exception.printStackTrace(); } } } } ```

• Anonymous

One more similar question I heard is to find all the combinations of input in a CSV file.

For example if the CSV file contained the following:
a,b,c
p,q
x,y,z

Find all combinations like apx, apy, apz…….cqz.

The above problem can be solved easily by your recursive logic.

This problem can be pretty easily solved using iteration. Have a one dimensional array which contains pointers to the current positions in each row. Initialize this array with 0. In an infinite loop, print the elements pointed by the array. Whenever this array reaches the last element for a particular row, initialize it back to 0 and increment the previous row’s pointer by one. Do this previous row’s increment until we reach a row which is not at the last element. The stop condition for this infinite loop will be when we are attempting to move beyond the last element of the first row.

Sometimes, I think the non-recursive functions might be given more priority than recursive functions even though recursive functions solve the problem more elegantly and easily. The non-recursive functions occupy less space sometimes (or most of the times). This comes handy when actually your application is writing the details to a stream rather than it itself doing the processing. For a case of a CSV file having m rows each having n columns, the non-recursive function has the space complexity of O(1), whereas for the non-recursive function will have O(n^m).

• Holden

I try to write, but I don’t know what our inputs should be …

• David

Actually, I believe the complexity is O(n*n!). True, you are permuting n! times but each permutation requires string calculations of O(n).

• Arden

You’re right David. Since the difference between n! and n*n! is minimal for large n, I didn’t mention it. Thanks for pointing out though.

• Cuneyt

In fact, you wouldn’t see O(n*n!) in most of the literature as it’s against the idea of Big Oh notation (i.e. simplification)

• abdus

Thaaaanks… Great explanation….

• Nathan

Nice! Here’s a similar non-recursive solution:

def permutations(word):
current = [word[0]]
nextLevel = []
for letter in word[1:]:
for fragment in current:
for i in range(len(fragment)+1):
nextLevel.append(fragment[:i] + letter + fragment[i:])
current = nextLevel
nextLevel = []
return current

• chirag

#include
#include
#include
#include
main()
{
char ch[10],temp;
int i,k=1,b,f;
clrscr();
printf(“enter the string”);
gets(ch);
for(i=1;i<=strlen(ch);i++)
{
k=k*i;
}
f=strlen(ch);
for(i=0;i<k;i++)
{
b=i%(f-1);
temp = ch[b+1];
ch[b+1]=ch[b];
ch[b]=temp;
printf("%s\n",ch);
}
getch();
}

• Romil

Interesting solution. I tried this for 4 letter string -abck and got duplicate answers after 12 permutations. The iteration starts with back and reaches abck on the twelfth iteration. Post that it repeats the same output.

I liked the solution and I think some minor change would this but still havent figured it out.

• dew

Hi Ardent. I loved your series of Programming interview Questions. Please post some more basic questions with solutions. That would be of great help!!!!

• CStubing

As far as I can tell, your method does not yield unique permutations when the same character appears in the original input more than once, for example: “aab”… you’ll return 6 permutations (N! for n=3), when there should really only be 3 permutations (3! / 2!*1!). It’s a good method, and there *is* a way to modify it to become correct… Can you? ;-)

• Mainul Mizan

This is a iterative java version. The idea is to generate all permutation of ch[0], then ch[0] and ch[1] and so on till ch[0] to ch[n].

public static ArrayList allStringsI(String s) {
ArrayList retVal = new ArrayList();

if (s == null || s.length() == 0)
return retVal;

char c;

for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);

ArrayList loop = retVal;
retVal = new ArrayList();

for (String st: loop){

for (int j = 1; j <= st.length(); j++)
retVal.add(st.substring(0, j) + c + st.substring(j));
}
}
return retVal;
}

• ram

What’s the complexity for this??

• Giacomo Drago

Great post, thank you!

After reading it, I had an idea of an alternative solution. It is not meant to be an improvement to this algorithm, in fact it’s completely different and much more complicated (quite useless for an interview ;)). However if you are interested, here it is: http://yatb.giacomodrago.com/en/post/12

• ajitsdeshpande

Hello,

Based on your recursive python implementation for finding string permutations, I am trying to write a python based iterative(non-recursive) implementation. So far I have got this code below which only works for a input string with 3 chars :( . Trying to expand and make it generic, any pointers would help.

def permutations_iter(word):

while True:

perms = []

result = []

char = word[0]

new_word = word[1:]

if len(new_word)==2:

perms = [new_word,”.join(reversed(new_word))]

for perm in perms:

#insert the character into every possible location

for i in range(len(perm)+1):

result.append(perm[:i] + char + perm[i:])

return result

if len(new_word)==2:

break;

• http://www.cnblogs.com/zhouyoulie/ 周游

/**************************************
Author:Zhou You
Time:2014.09.14
**************************************/

#include
#include
using namespace std;

void OutputPermutation(string &strdata,unsigned ileft,unsigned iright)
{
if(ileft>iright) return;
if(ileft==iright){
cout<<strdata<<endl;
return;
}

for(unsigned i=ileft;i>strdata;
OutputPermutation(strdata,0,strdata.length()-1);
}

int main()
{
freopen(“txt.in”,”r”,stdin);
freopen(“txt.out”,”w”,stdout);
unsigned case_num= 0;
cin>>case_num;
for(unsigned i=0;i<case_num;++i){
Solve();
}

return 0;
}

• Raf

great posts!
unless I misunderstood the problem, I was having some issues implementing your algo to get all permutations. seems like the first character never gets written out. In my tests I implemented the following in JS which appears to work for all combinations. (small tweak to your algo)

function permutate(word){
if (!word || !word.length) return;
print(word);
if (word.length == 1) return;
var c = word[0];
var rem = word.substr(1);
for (i in rem+1){
if (i==0) continue;
var perm = rem.substr(0, i) + c + rem.substr(i);
print(perm);
}
permutate(rem);
print(c);
}

• rightaw2

With C# select method and a tiny lambda expression, this gets really simple:

static List permutations(string thisString)
{
List myResult = new List();
if (thisString.Length <= 1)
{