全排列（数字重复与不重复）问题的递归与非递归代码

全排列
给定一个数字列表，返回其所有可能的排列。

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

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

递归代码

class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        allResult = []
        result = []
        self.permutes(nums, result, allResult)
        return allResult

    def permutes(self, nums, result, allResult):
        # write your code here
        if nums == []:
            new_list = []
            for i in result:
                new_list.append(i)
            allResult.append(new_list)
        for num in nums:
            result.append(num)
            new_nums = []
            for x in nums:
                if x!=num:
                    new_nums.append(x)
            self.permutes(new_nums, result, allResult)
            result.pop()
        return

非递归代码（仅用于数字不重复的全排列问题中，后来改进）

class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        nums_used = [0]*len(nums)
        nums_used_in_stack = [[] for j in range(len(nums))]
        stack = []
        allResult = []
        while(True):
            for key, num in enumerate(nums):
                if(nums_used[key] == 0):
                    if num not in nums_used_in_stack[len(stack)]:
                        stack.append(num)
                        nums_used[key] = 1
                        nums_used_in_stack[len(stack) - 1].append(num)
                        try:
                            nums_used_in_stack[len(stack)] = []
                        except IndexError:
                            pass

            if(len(stack) == len(nums)):
                result = []
                for i in stack:
                    result.append(i)
                allResult.append(result)

                while (True):
                    try:
                        x = stack.pop()
                    except IndexError:
                        return allResult
                    for key2, num2 in enumerate(nums):
                        if num2 == x:
                            nums_used[key2] = 0

                    flag = 0
                    for key3, num3 in enumerate(nums):
                        if nums_used[key3] == 0 and num3 not in nums_used_in_stack[len(stack)]:
                            flag = 1
                            break
                        else:
                            flag = 0
                    if(flag == 0):
                        continue
                    else:
                        break

附上题目来源：
https://www.lintcode.com/problem/kth-largest-element/description

带重复元素的排列
给出一个具有重复数字的列表，找出列表所有不同的排列。

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

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

挑战
使用递归和非递归分别来完成该题。

递归代码

class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permuteUnique(self, nums):
        allResult = []
        result = []
        self.permutes(nums, result, allResult)
        return allResult

    def permutes(self, nums, result, allResult):
        # write your code here
        nums_used = []
        if nums == []:
            new_list = []
            for i in result:
                new_list.append(i)
            allResult.append(new_list)
        for index in range(0, len(nums)):
            if nums[index] not in nums_used:
                result.append(nums[index])
                nums_used.append(nums[index])
                new_nums = []
                for x in nums:
                    new_nums.append(x)
                del new_nums[index]
                self.permutes(new_nums, result, allResult)
                result.pop()
        return

非递归代码(改进之后，可用于数字重复或不重复的全排列问题中)

class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permuteUnique(self, nums):
        nums_used = [0]*len(nums)
        nums_used_in_stack = [[] for j in range(len(nums))]
        stack = []
        allResult = []
        while(True):
            for key, num in enumerate(nums):
                if(nums_used[key] == 0):
                    if num not in nums_used_in_stack[len(stack)]:
                        stack.append([key, num])
                        nums_used[key] = 1
                        nums_used_in_stack[len(stack) - 1].append(num)
                        try:
                            nums_used_in_stack[len(stack)] = []
                        except IndexError:
                            pass

            if(len(stack) == len(nums)):
                result = []
                for i in stack:
                    result.append(i[1])
                allResult.append(result)

                while (True):
                    try:
                        x = stack.pop()[0]
                    except IndexError:
                        return allResult
                    for key2, num2 in enumerate(nums):
                        if key2 == x:
                            nums_used[key2] = 0

                    flag = 0
                    for key3, num3 in enumerate(nums):
                        if nums_used[key3] == 0 and num3 not in nums_used_in_stack[len(stack)]:
                            flag = 1
                            break
                        else:
                            flag = 0
                    if(flag == 0):
                        continue
                    else:
                        break

附上题目来源：
https://www.lintcode.com/problem/permutations-ii/description