CODEWITHSUNDEEP
pythonalgorithmpython-2.7permutation
Prakash N
Prakash N

Reputation: 1070

Permutation: return the kth permutation

I know there is a O(n) time complexity solution for this problem, here for example.

I am just curious why my naive approach in O(2^n) is not working in Python.

Algorithm:

I am just finding the permutations recursively and when the kth element is added, i am returning it. However I get the return result as None. I am not sure why None is returned by my function.

class Solution(object):

    # Time complexity O(2 ^ n)
    def getPermutation(self, n, k):
        char_list = map(str, range(1, n + 1)) #convert to strin
        used = [False] * len(char_list)
        result = []
        kthArray = self._getPermutation_helper(result, char_list, used, [], k)
        print kthArray #kthArray is always None

    def _getPermutation_helper(self, result, char_list, used, cur,  k):
        if len(char_list) == len(cur):
            result.append(cur + [])
            print len(result)
            print cur
        if len(result) == k:
            print "cur in kth is {0}".format(cur)
            return cur #cur is printed correctly but not returned
        for i in range(len(char_list)):
            if not used[i]:
                cur.append(char_list[i])
                used[i] = True
                self._getPermutation_helper(result, char_list, used, cur, k)
                # back track
                used[i] = False
                cur.remove(char_list[i])
def main():
    pgm = Solution()
    pgm.getPermutation(3, 6)
    
if __name__ == "__main__":
    main()

Why isn't the correct value returned?

Upvotes: 4

Views: 389

Answers (1)

IVlad
IVlad

Reputation: 43467

Because you are returning cur to a previous call of the same function, from which you don't return it further down to the first call.

You need to keep propagating the found solution until the first call. For example:

    for i in range(len(char_list)):
        if not used[i]:
            cur.append(char_list[i])
            used[i] = True

            # Here we do a recursive call, which might find the answer we're looking for.
            # So we save its return value and, if it's not None, we return it.
            r = self._getPermutation_helper(result, char_list, used, cur, k)
            if r is not None:
                return r

Upvotes: 3

Related Questions