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?

https://www.youtube.com/watch?v=nc8FBHYrjVw

Youtube thumbnail

&list=PLD9781AC5EBC9FA16&index=12

1 Answer

Relevance
  • Alan
    Lv 7
    2 weeks ago
    Favorite Answer

    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

    Link to

    c++ , version of the program    

    https://www.dropbox.com/s/vtadxt2vcxcl5cj/Permappl...

Still have questions? Get your answers by asking now.