全排列

题目描述：给定一个数字列表，返回其所有可能的排列。

样例：给出一个列表[1,2,3]，其全排列为：

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]

]

排列的规则应该是这样的，假设由n个数字组成，那么，我们先拿出第一个数，设为a，然后让其他的数字做全排列，排列出来的结果中，在每个结果的第一位添加a即可。那么，拿出a之后的数组是如何生成全排列的呢，也是通过一样的方法，先拿出一个，令其他的生成全排列，再把拿出的元素添加进去。这正是典型的递归。

所以，用递归的方法，我们可以写出代码：

class Solution:
    """
    @param nums: A list of Integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        result = []
        if nums is None:
            return result
        if len(nums) == 0:
            result.append([])
        for ele in nums:
            temp_nums = nums[:]
            temp_nums.remove(ele)
            for i in self.permute(temp_nums):
                i.insert(0, ele)
                result.append(i)
        return result
        # write your code here

需要注意两点：1是触底的条件，当nums是个空列表的时候，返回的应该是[[]]，而不是[]；2是第13行的代码意思是复制数组，也就是重新生成一个数组，这个数组中的任何操作，不会影响其所拷贝的数组。这也属于是Python语言的特性了，因为直接赋值，只会传递指针，就是两个名字指向了同一个地址，而不会生成一个新的数组。

举个例子：

array1 = [1, 2, 3]
array2 = array1
array2.append(4)
print(array2)
print(array1)

输出结果为：[1, 2, 3, 4], [1, 2, 3, 4]，因为array1和array2两个引用指向的是同一个地址

而：

array1 = [1, 2, 3]
array3 = array1[:]
array3.append(4)
print(array1)
print(array3)

输出结果为：[1, 2, 3], [1, 2, 3, 4]，array3是复制array1得到的，和array1是两个完全不相关的列表

当然，这道题也可以不用递归。之前，我们学过怎样求取一个排列的下一个排列（详见：点击打开链接），那这里就很简单了，我们不妨可以就按字典序一个个输出排列，集合到一起就是结果，代码很简单，直接调用之前的函数就行：

class Solution:
    """
    @param nums: A list of Integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        result = []
        if nums is None:
            return result
        nums.sort()
        n = len(nums)
        i = 0

        while i < self.fact(n):
            temp = nums[:]
            result.append(temp)
            self.nextPermutation(nums)
            i += 1
        return result

    def nextPermutation(self, nums):
        n = len(nums)
        if n == 0 or n == 1:
            return
        right_index = n - 1
        pivot = 0
        while right_index >= 0:
            if right_index - 1 >= 0 and nums[right_index] > nums[right_index - 1]:
                pivot = right_index - 1
                break
            elif right_index == 0:
                pivot = right_index - 1
                break
            else:
                right_index -= 1
        if pivot < 0:
            nums.sort()
        else:
            right_index = n - 1
            while right_index >= 0:
                if nums[right_index] > nums[pivot]:
                    nums[right_index], nums[pivot] = nums[pivot], nums[right_index]
                    break
                else:
                    right_index -= 1
            left = pivot + 1
            right = n - 1
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

    def fact(self, n):
        if n == 0:
            return 0
        result = 1
        for i in range(1, n + 1):
            result *= i
        return result
        # write your code here

函数nextPermutation()是之前我们写过的东西，这里直接拿来用了，所以略过不讲（详见：点击打开链接），fact()函数是求取整数的阶乘。