Python Program to Print All Permutations of a String in Lexicographic Order using Recursion














































Python Program to Print All Permutations of a String in Lexicographic Order using Recursion



The Code:
class string_permutation:
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(2n) 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(2n)
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
the oop concept:
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

More Articles of Kislay Kanti Dhar:

Name Views Likes
Python Boto3:glacier remove tags from vault 178 0
Python Boto3:aws glacier delete vault access policy 153 0
Python Boto3:aws glacier get and set vault access policy 155 0
Python Boto3: aws glacier describe vault 169 0
Python boto3:aws glacier adding tags to vaults and listing them 148 0
Python Boto3 : getting list of Vaults of aws Glacier 203 0
Python boto3 : create aws glacier vault 233 0
configuring boto3 245 1
Rendering Html5 forms and getting forms data with Python Flask 296 0
Python Bisect module:sorting on the go 249 0
Python heapq: The library for implementing heaps and heapsort 191 0
Python DB2 Drop table 303 0
Python DB2 select from table 239 0
Python DB2 multiple insert record into table 276 0
Python Collections : using deque 452 0
Python Project:Making a voice recorder with Python 1696 4
Python DB2 how to get the tuples using ibm_db.fetch_tuple 467 0
Python Collections: understanding the counter 202 0
Python Collections:understanding ChainMap 276 0
Python Enum: exploring the enum datastructure 268 0
DB2: Inserting values into an existing table using Python 899 0
DB2: Creating a table with python code 775 0
DB2 :connecting IBM database server to python 754 0
IBM DB2: an introduction 228 0
Python UDP Client Server program 365 0
Python Socket: basic functions and concepts 256 0
Python TCP Client Server program 539 0
Python Project: Attendance Manager GUI application made with Tkinter 798 1
Python Program to get Google search results 205 0
Python Program for opening google search 189 0
Python program to find out the disk speed 257 0
Python Matplotlib scatter plots 294 1
Python Matplotlib plotting bar graphs 441 0
Python Matplotlib plotting a pie chart 364 0
Python Matplotlib and plotting sin and cos graphs 1326 0
Python Numpy Loading data files and operation 400 0
Python Tkinter making a gui application to count characters of input text 791 1
Python Numpy polynomials operation and implementation in Matplotlib 475 0
Python Numpy Elementwise operations 457 0
Python Numpy Indexing and slicing 299 1
Python Numpy basic visualization using Matplotlib library 418 0
Python Numpy use of ones ,zeros , eye and diag 385 1
Python Numpy use of arange and linspace functions 754 1
Python Numpy understanding the dimension of arrays and shapes using shape and ndim 727 1
Python Numpy creating arrays using array function 286 1
Python Numpy an introduction 348 1
Python Program to Print All Permutations of a String in Lexicographic Order using Recursion 1015 24

Comments

  • Kislay
    9-May-2019 12:06:16 AM
    //Enter Your Comment Here...