search
Log In
3 votes
317 views
How to generate permutation of a string? What will be the complexity?
in Algorithm Challenges
retagged by
317 views
0
Can it be done by backtracking?
0
Try recursion. Permute for length l-1, add the last char at each position of these permuted strings.
1
s is the starting index of the string,e is the ending index of the string.

void permute(char *x, int s, int e)
{
   int i;
   if (s== e)
     printf("%s\n", x);
   else
   {
       for (i = s; i <= e; i++)
       {
          swap((x+s), (x+i));
          permute(x, s+1, e);
          swap((x+s), (x+i));
       }
   }
}

1 Answer

3 votes

There are man methods and best case complexity is $O(n!)$ as there are $n!$ permutations for a string. I'm using Java code as it is recommended for most top tier interviews. (C is not suitable for many interviews as in Google).

Here permute and permute1 are two different permutation methods. 

import java.io.*;
import java.util.ArrayList;

public class permuteString{


        ArrayList<String> permute(String str){
                ArrayList<String> al = new ArrayList<String>();
                if(str.length() == 0)
                {
                        al.add("");
                        return al;
                }
                ArrayList<String> words = permute(str.substring(1, str.length()));
                char    c = str.charAt(0);
                for(String word: words)
                {
                        for(int i = 0; i<= word.length(); i++)
                                al.add(word.substring(0, i)+ c+ word.substring(i, word.length()));

                }
                return al       ;

        }

        void permute1(String prefix, String s) {
                if(s.length() == 0)
                {
                        System.out.println(prefix);
                }
                for(int i =0; i < s.length(); i++)
                {
                        permute1(prefix+s.charAt(i), s.substring(0,i)+s.substring(i+1, s.length()));
                }

        }
public static void main(String args[]) {
                permuteString mystring = new permuteString(); //Initialize class
                mystring.permute1("", args[0]);
                System.out.println("____________________________");
                ArrayList<String> words =       mystring.permute(args[0]);
                for(String word:words)
                        System.out.println(word);

        }

}
0
Sir, Is not this can be solved by using Tower of Hanoi recursion.?
0
How?
0
void permute(char *x, int s, int e)
{
   int i;
   if (s== e)
     printf("%s\n", x);
   else
   {
       for (i = s; i <= e; i++)
       {
          swap((x+s), (x+i));
          permute(x, s+1, e);
          swap((x+s), (x+i));
       }
   }
}

Related questions

0 votes
1 answer
1
142 views
output: Ssihtllun sillun ehtllun elbatllun import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { public static void main (String[] args) throws java.lang.Exception { Codechef c=new Codechef(); String res=c.reverseword ... = ""; for(int i=0;i<arr.length; i++){ if(i>0) ans+=" "; ans+=arr[i]; } return ans; } }
asked Aug 9, 2015 in Java Baljeet Sohal 1 142 views
2 votes
1 answer
2
655 views
Given an array with possible repeating elements you have to rearrange such that elements are alternatively decreasing and increasing (strict increase/decrease). For example, suppose the given array is 1 1 2 3 4 5 one possible answer would be 2 1 3 1 5 4. Assumption: Solution do exist for any given input. Hint: Try to avoid sorting.
asked May 27, 2016 in Algorithm Challenges Arjun 655 views
0 votes
1 answer
3
0 votes
1 answer
4
86 views
Consider a bit-string of length 10 containing only 0 and 1. The number of string contain exactly 3 0’s or exactly 31’s are ________
asked Dec 22, 2017 in Mathematical Logic Jaspreet Kaur Bains 86 views
...