排列组合：返回第k个排列

Question

我知道这个问题有一个时间复杂度为 O(n) 的解决方案，比如 这里。

我只是好奇为什么我的朴素方法在 Python 中的时间复杂度为 O(2^n) 时不能工作。

算法：

我只是递归地找到排列，当加入第 k 个元素时，就将其返回。但是，我得到的返回结果是 None。我不确定为什么我的函数会返回 None。

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()

为什么没有返回正确的值？

- Prakash N

---

请查看此实现：http://code.activestate.com/recipes/126037-getting-nth-permutation-of-a-sequence/。 - erip

你在 _getPermutation_helper() 的多个路径中没有返回任何内容，如果跟随其中一个路径，则返回值为 None，这很可能是你正在打印的内容。 - AChampion

Answer 1

因为你将 cur 返回到同一函数的先前调用，但在那里却没有将其进一步返回到第一个调用。

你需要继续传播找到的解决方案直到第一个调用。例如：

    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

- IVlad

---

就编程而言，FWIW，“r is not None”比“r！= None”更受推崇，因为测试对象身份比比较对象值更便宜。 - PM 2Ring

@PM2Ring没错，我已经把它改成了r不是None。谢谢！ - IVlad