# What program is this IIT teacher writing at 38:54 in this video?

He is doing some recursion stuffs, but I don't seem to understand what he is doing. He also tried to explain it, but it is very unconvincing teaching. So, I wanted to google and learn, what he was trying to teach. Can anyone watch 38:54 of the video and tell me what he is doing?

&list=PLD9781AC5EBC9FA16&index=12

Relevance
• Alan
Lv 7
2 weeks ago

What the program does is

find and print all permutation of a

set of n characters in groups of r

so if you enter n =3 , r = 2

and

character set (a,b,c)

You get permutations

All possible combinations of 2 of the 3 characters

ab ac ba bc ca cb

Summary in English for n -3 and r=2

and "abc" as the string

it picks 1st character

a

then, it adds each of the remaining characters to it

ab

then

ac

then it picks the 2nd character b

b

then , it adds each of the remaining characters to it

ba

then

bc .

then, it picks the 3rd character

c

then, it adds each of the remaining characters to it

ca

then

cb

So almost step by step describing the routine

So how does his subroutine do this.

so given

list = {a,b,c,\0}

n = 3

r = 2

1st run ,

Level 1 (1st call to permut.)

n = 3 , r = 2 ,m= 0, i = 0;

list = {a,b,c,\n}

it put {a} into PERM[m=0] = 'a' ;

then, it delete 0th (or 1st if you want character)

from list and stores this in

NEWLIST = 'bc'

then, it call itself

########2nd level

########with calling parameters

########NEWLIST ='bc' , n=2 , r=1 = 1 ,m = 1 , PERM='a'

########i = 0

########Then , the routine

########PERM[m =1 ] = b (0th(counting from 0) or 1st charcter in 'bc' )

########PERM = 'ab'

########deletes 1st character from LIST = 'bc'

########creating NEWLIST = "c'

########then, it calls itself again

::::::::::::::::3rd Level

::::::::::::::::with parameters, NEWLIST = 'c', n=1, r=0 , m=2

::::::::::::::::adds "\0" to end the string

::::::::::::::::Then, it prints PERM = 'ab'

::::::::::::::::it returns to PERMUT at the 2nd Level

########2nd Level

########at the 2nd level with LIST ='bc' i = 1 , PERM ='ab'

########PERM[ m =1 ] = LIST[ 1] = ' c'

########PERM = 'ac'

########then, it deletes the 1th character from List (2nd character counting from 1)

########creating NEWLIST = 'b'

########then, it calls itself again

::::::::::::::::3rd LEVEL

::::::::::::::::with parameters, NEWLIST ='b', n = 1, r =0 , m 2

::::::::::::::::Then, it prints PERM = 'ab'

::::::::::::::::it returns to PERMUT at the 2nd Level

::::::::::::::::since loop was from 0 to 1

########it returns to Level 1 call of PERMUT

Level 1 (1st call to permut.)

n = 3 , r = 2 ,m= 0, i = 1;

list = {a,b,c,\n}

it put {a} into PERM[m=0] = LIST[1] = 'b' ;

then, it delete 2nd character if you want character counting from 1 (1th from zero)

from list and stores this in

NEWLIST = 'ac'

then, it call itself

########2nd level

########with calling parameters

########NEWLIST ='ac' , n=2 , r=1 = 1 ,m = 1 , PERM='b'

########i = 0

########Then , the routine

########PERM[m =1 ] = a (0th(counting from 0) or 1st charcter in 'bc' )

########PERM = 'ba'

########deletes 1st character from LIST = 'ac'

########creating NEWLIST = "c'

########then, it calls itself again

:::::::::::::::: 3rd Level

:::::::::::::::: with parameters, NEWLIST = 'c', n=1, r=0 , m=2

:::::::::::::::: adds "\0" to end the string

:::::::::::::::: Then, it prints PERM = 'ba'

:::::::::::::::: it returns to PERMUT at the 2nd Level

########2nd Level

########i= 1 now m = 1

########LIST = 'ac' ;

########PERM= 'b'

########at the 2nd level

########PERM[ m =1 ] = LIST[ 1] = ' c'

########PERM = 'bc'

########then, it deletes the 2nd character counting from 1 (1th from 0 )

########creating NEWLIST = 'a'

########then, it calls itself again

:::::::::::::::: 3rd LEVEL

:::::::::::::::: with parameters, NEWLIST ='a', n = 1, r =0 , m 2

:::::::::::::::: Then, it prints PERM = 'bc'

:::::::::::::::: it returns to PERMUT at the 2nd Level

Level 1 (1st call to permut.)

n = 3 , r = 2 ,m= 0, i = 2;

list = {a,b,c,\n}

it put {a} into PERM[m=0] = LIST[2] = 'c' ;

then, it delete 3rd character if you want character counting from 1 (2nd from zero)

from list and stores this in

NEWLIST = 'ab'

then, it call itself

########2nd level

########with calling parameters

########NEWLIST ='ab' , n=2 , r=1 = 1 ,m = 1 , PERM='b'

########i = 0

########Then , the routine

########PERM[m =1 ] = a ( 1st charcter in 'ab' )

########PERM = 'ca'

########deletes 1st character from LIST = 'ab'

########creating NEWLIST = 'a'

########then, it calls itself again

::::::::::::::::3rd Level

::::::::::::::::with parameters, NEWLIST = 'a', n=1, r=0 , m=2

::::::::::::::::adds "\0" to end the string

::::::::::::::::Then, it prints PERM = 'ca'

::::::::::::::::it returns to PERMUT at the 2nd Level

########2nd Level

########i= 1 now m = 1

########LIST = 'ab' ;

########PERM= 'c'

########at the 2nd level

########PERM[ m =1 ] = LIST[ 1] = 'b'

########PERM = 'cb'

########then, it deletes the 2nd character counting from 1 (1th from 0 )

########creating NEWLIST = 'c'

########then, it calls itself again

::::::::::::::::3rd LEVEL

::::::::::::::::with parameters, NEWLIST ='c', n = 1, r =0 , m 2

::::::::::::::::Then, it prints PERM = 'cb'

::::::::::::::::it returns to PERMUT at the 2nd Level

::::::::::::::::since loop is from 0 to 1

::::::::::::::::it returns to 2nd level

########2nd Level , since loop is from 0 to 1

########It returns to Level 1

Level 1 , it is down since loop is 0 to 2

I have a version of his routine

in C++ with scanf replace with cin command replacing scanf commands

You need to enter n and r separately