def __init__(self,s):

self.s=s;#to store the string

self.n=len(self.s)#to store the length of the string

self.list_of_generated_strings=list()#to store the generated string and also for sorting

def rec(self,l):

d=l

for j in range(0,self.n):

if j not in d:

d.append(j)

self.rec(d)

if(len(d)==self.n):

st=''

for q in d:

st=st+self.s[q]

self.list_of_generated_strings.append(st)

d.pop()

def execute(self):

for i in range(0,self.n):

l=list()

l.append(i)

self.rec(l)

def get_the_strings(self):

self.list_of_generated_strings.sort()

print(self.list_of_generated_strings)

#the main block

p=string_permutation(input('Enter the string:'))

p.execute()

p.get_the_strings()

The code provided is

in python3 . I used Python 3.7.1. The given problem was to accept a

string ,find all possible permutations and arrange them in

lexicographical order or alphabetical order.

Well if a guy is

into algorithm subject for a time , it is for sure that he or she may

have heard about NP-hard problem.(And suddenly our minds shifts to

other problems,big recursive trees of n-queen problem,graph colouring

problem). All the NP- hard problems are difficult to sove because

most of them have O(2^{n}) complexity. Thus the most time

taking algorithms of all. All these algorithms have same procedure of

finding permutations one way or other ,hence similar to the given

problem. Therefore this problem is also NP-hard.

So how we do it.

let us take an example of a small problem so it will be easily

understandable.

Let a string be

"cat" so approach can be like:

So basically the

idea is:

1) store the string.

2)get the length

3)if the length is

described as n then we will get all possible arrangements from 0 to

n-1

4)The reason is

getting numbers from 0 to n-1 will give us access to the characters

of the inserted string

Now visualise this

as like this:

s="cat"

n=3

012,021,120,102,210,201

will be the combination

now access the

characters with created_string=s[0]+s[1]+s[2]..... etc

Since it is a O(2^{n})

algorithm implementation,execution can be a bit bumpy, as for we need

all the permutation then number of expected outputs will be factorial

of n,

ex:

cat,n=3,n!=6,cat,cta,atc,act,tac,tca a total of 6 outputs

code gives output

quickly till n=9 but slows for n=10 and starts slowing down for

longer strings

here are some

outputs:

for a 6 letter word

it stops for some moment in 10 letter word

But after sometimes output bursts out

class members are s,n,list_of_generated_strings and class functions are execute,get_the_strings,rec,the __init__ is used to initialise which is a part of constructor

## Comments

## Kislay

9-May-2019 12:06:16 AM