Print all permutations of a given string.

Question

Pallavi · Accepted Answer

# include 
# include  
 
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s
", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 
 
/* Driver program to test above functions */
int main()
{
   char a[] = "ABC";
   permute(a, 0, 2);
   getchar();
   return 0;
}

Anonymous · Answer

a string of N characaters will have following number of string combination

Np1 + Np2 + Np2+...NpN

Jimmy · Answer

Using recursion we can solve this. I am giving the pesudo code with a small example. 
let the string be "abc".  I am showing the recursive call within the bracket itself. Just to understand. Don't confuse that this is a code inside permute function. 
permute(abc)
{
----level  1-----
letter saved at this level is  = a;
all combination List obtained at this level = permute(bc);

  after the call returns put the saved letter {a} at each position in each entry and do the same for all entry in the list 
	  List obtained here is only bc and cb; 
	  that means put a every position of the return bc and cb ----> for bc {abc,back,bcd} and for cb {cab,cab,cba}
	 return all the entries. 

At the highest level you will get all the permutation of the string. 

--------------level 2-----------
               letter saved  = b ;
               all combination List obtained at this level = permute(c);
	 
	   after the call returns put the saved letter at each position in each entry and do the same for all entry in the list 
	  List obtained here is only c; 
	  that means put b every position of the return c --> bc{putting b before c} and cb{putting b after c} 
	 return bc and cb. 
		
		--------------level 3-----------
              	 letter saved  = c ;
               	all combination List obtained at this level = 1; //Here it only c is returned
               	Last letter is returned as this is only 1 combination exist -- base condition of recursion. 
	  

}

Anonymous · Answer

C# code. I'm a tester, so my code is a bit rusty, but the algorithm works.

public static void Permutations(string orgStr)
        {
            List permutations = new List();
            _perm(orgStr.ToCharArray(), String.Empty, ref permutations);

            foreach (string str in permutations)
            {
                Console.WriteLine(str);
            }
        }

        private static void _perm(char[] sample, string filled, ref List permutations)
        {
            if (sample.Length == 1)
            {
                string perm = String.Format("{0}{1}", filled, new string(sample));
                permutations.Add(perm);
            }
            else
            {
                for (int i = 0; i  i)
                        {
                            newSample[j-1] = sample[j];
                        }
                        else
                        {
                            newSample[j] = sample[j];
                        }
                    }

                    _perm(newSample, newFilled, ref permutations);
                }
            }
        }

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches