The Gateway to Computer Science Excellence
+3 votes
253 views
How to generate permutation of a string? What will be the complexity?
in Algorithm Challenges by Veteran (431k points)
retagged by | 253 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.
0
+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);

        }

}
by Veteran (431k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,290 answers
198,197 comments
104,876 users