5 Questions for TYL on Strings(permutations)


1.      Write a program to find a Permutation of a given string (Printing various combinations of characters in the string)
Constraint  : use string inbuilt function


Okay, so last semester, I've seen students struggling with this during Java TYL and this is never covered during the class so it makes it very difficult.

So what is a permutation?

A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. The number of permutations on a set of n elements is given by n!  
(https://mathworld.wolfram.com/Permutation.html)

So if you have s= "ABC", the permutation would be
ABC
ACB
BAC
BCA
CAB
CBA
Number of resultant strings are 3! = 6
And lexicographic order is nothing but dictionary order... eg. put BAC before BCA...

So the basic algorithm for this would be:
Remove each element from the n elements one at a time, then append it to the (n-1)! remaining permutations. (https://www.topcoder.com/generating-permutations/)

When we do this recursively...
Notice
ABC ACB - A is fixed
BAC BCA - B is fixed
CAB CBA - C is fixed.

So we write one swap for n iterations to bring each character to the front.
for the remaining letters, however many, we swap, reduce, swap until we've reached the end so
if in the first iteration we're going from k to n-1, where k=0, n-1 =2
we  increment k by 1,
stop when k=n-1

once we have generated all the strings with the first fixed character, we swap back to original string then restart the process.

                                                      A                      B                            C
                                                    /                           |                               \
                                                  /                             |                                \
                                                /                               |                                 \
                       A is fixed, ABC                         B is fixed, BAC               C is fixed, CBA
                    (k=0, i=0, swap)                             (k=1, i=0, swap)              (k=2, i=0 swap
                       /               \                                          /       \                                 /   \
                      /                 \                                        /         \                              /      \
     (k=1, i=1, swap)     (k=1, i=2, swap)                  /            \                           /          \
            ABC                     ACB                          BAC         BCA             CBA       CAB
     
            k=2 
       k=n-1, stop

The program will look like this:

def permutation(a,n,k=0):
    if k == n-1:
        print("".join(a))
        return;
        
    for i in range(k,n):
        a[k], a[i] = a[i],a[k]
        permutation(a,n,k+1)
        a[k], a[i] = a[i],a[k]

 s="ABC"
permutation(list(s),len(s))

Output:
ABC
ACB
BAC
BCA
CBA
CAB

Other things that I've not taught yet in class...
In  def permutation(a,n,k=0):k=0 is the default value if we're not passing anything during the function call.
We're using "".join(a) to essentially convert a list to a printable string.The method is invoked on the separator... we're using as an empty string so it appends all items together... try these out:
>>> a=['A','B','C']
>>> ':'.join(a)
'A:B:C'
>>> ''.join(a)
'ABC'
>>>

There are other alternate methods... you can look those up here:https://www.topcoder.com/generating-permutations/


If you can remember some packages, the itertools package gives you a permutation function and if you're allowed to use it, then you can write the following code also.  The output is lexicographically ordered also.

Alternate program using itertools
import itertools as it
s="ABC"
ps = list(it.permutations(s))

 for item in ps:
    print("".join(item))

 Output:
ABC
ACB
BAC
BCA
CAB
CBA


Comments

Post a Comment

Popular posts from this blog

TYL - Food Corner Program

Food Corner Program. We will make this program more robust after you learn try-catch.  For now, we will calculate for only 1 order.  Again, later you can use loops to calculate for many orders.  As we have not learnt any data structures as lists, dictionaries etc, we will not use them now. FoodCorner home delivers vegetarian and non-vegetarian combos to its customer based on order. A vegetarian combo costs Rs.120 per plate and a non-vegetarian combo costs Rs.150 per plate. Their non-veg combo is really famous that they get more orders for their non-vegetarian combo than the vegetarian combo. Apart from the cost per plate of food, customers are also charged for home delivery based on the distance in kms from the restaurant to the delivery point. The delivery charges are as mentioned below: Distance in kms          Delivery charge in Rs. Per kms For first 3 kms                       ...
Read more

Classes and objects solution

Image
Question 1 Write a definition for Student class Define __init__(self, marks=[]) for the Student class Define add_marks(self,lst) that appends mark to the marks list Create two students, s1 and s2. Add [25,45,65] to s1 Print marks of s1 and s2 Observe what happens? Fix the code. Initial Implementation class Student:     def __init__(self, marks=[]):         self.marks = marks     def add_marks(self,lst):         self.marks.extend(lst) s1= Student() s2=Student() s1.add_marks([25,45,65]) print('Contents of s1',s1.marks) print('Contents of s2',s2.marks) Output: Contents of s1 [25, 45, 65] Contents of s2 [25, 45, 65] Observation: list is getting added to s1, but s2 also shows the same contents.  What is expected is an empty list for s2 but s1 consisting of [25,45,65] Why this happens? https://stackoverflow.com/questions/4841782/python-constructor-and-default-value Solution: def __ini...
Read more

TYL - Salary Hike - Python Problem

Salary Hike Problem using Python We are not going to use any complex data structures in Python here. You will need to know the if else construct.  After we learn try... catch we will make this program more robust. if  condition:      statements      .... elif condition:      statements     ... ... else:     statement An organization has decided to provide salary hike to its employees based on their job level. Employees can be in job levels 3, 4 or 5. Hike percentage based on job levels are given below: Job level         Hike Percentage (applicable on current salary) 3                        15 4                         7 5                         5 In case of invalid job level, consider hike percentage to be ...
Read more