pythonfor-looprecursiontreevisualize

visualisation of recursion in a for loop in Python


I'm having trouble drawing a recursion tree for the following permutation code:

def permut(array):

    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        print permutation, array
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

Let's say my array is 'mick' then I get the following print outs for permutation and array:

k and ck

ck and ick

kc and ick

ick and mick

I understand it until 'k' and 'ck' (as when array = 'ck' len(arraw[1:]) == 1) but how do we ever get 'ick' as an array in the recursion? Could you visualize this anyhow? Thanks a lot for any tips!


Solution

  • permut('Mick')                 # recursion: for permutation in permut('ick')
        permut('ick')              # recursion: for permutation in permut('ck')
            permut('ck')           # recursion: for permutation in permut('k')
                permut('k')        # return ['k']
            permut('ck')           # continue from the loop
                                   # print each element of ['k'] with 'ck'
                                   # return res, which is ['ck', 'kc']
        permut('ick')              # continue from the loop
                                   # print each of ['ck', 'kc'] with 'ick'
                                   # return res, which is ['ick', 'cik', 'cki', 'ikc', 'kic', 'kci']
    permut('Mick')                 # continue from loop
                                   # print each of the above elements + 'Mick' individually
                                   # return res, which is... long
    

    The above basically permutes all letters in the word, which can be simply achieved with

    >>> import itertools as it
    >>> res = list(''.join(p) for p in it.permutations('Mick'))
    >>> print res
    ['Mick', 'Mikc', 'Mcik', 'Mcki', 'Mkic', 'Mkci', 'iMck', 'iMkc', 'icMk', 'ickM', 'ikMc', 'ikcM', 'cMik', 'cMki', 'ciMk', 'cikM', 'ckMi', 'ckiM', 'kMic', 'kMci', 'kiMc', 'kicM', 'kcMi', 'kciM']