对于Python，我们可以使用itertools并导入排列和组合来解决问题

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))

这是初始排序后生成排列的渐近最优方式O（n*n！）。

有n个！最多进行一次置换，且具有下一次置换（..），以O（n）时间复杂度运行

在3个步骤中，

找到最大的j，使a[j]可以增加以最小可行量增加a[j]找到扩展新a[0..j]的字典最少方法

'''
Lexicographic permutation generation

consider example array state of [1,5,6,4,3,2] for sorted [1,2,3,4,5,6]
after 56432(treat as number) ->nothing larger than 6432(using 6,4,3,2) beginning with 5
so 6 is next larger and 2345(least using numbers other than 6)
so [1, 6,2,3,4,5]
'''
def hasNextPermutation(array, len):
    ' Base Condition '
    if(len ==1):
        return False
    '''
    Set j = last-2 and find first j such that a[j] < a[j+1]
    If no such j(j==-1) then we have visited all permutations
    after this step a[j+1]>=..>=a[len-1] and a[j]<a[j+1]

    a[j]=5 or j=1, 6>5>4>3>2
    '''
    j = len -2
    while (j >= 0 and array[j] >= array[j + 1]):
        j= j-1
    if(j==-1):
        return False
    # print(f"After step 2 for j {j}  {array}")
    '''
    decrease l (from n-1 to j) repeatedly until a[j]<a[l]
    Then swap a[j], a[l]
    a[l] is the smallest element > a[j] that can follow a[l]...a[j-1] in permutation
    before swap we have a[j+1]>=..>=a[l-1]>=a[l]>a[j]>=a[l+1]>=..>=a[len-1]
    after swap -> a[j+1]>=..>=a[l-1]>=a[j]>a[l]>=a[l+1]>=..>=a[len-1]

    a[l]=6 or l=2, j=1 just before swap [1, 5, 6, 4, 3, 2] 
    after swap [1, 6, 5, 4, 3, 2] a[l]=5, a[j]=6
    '''
    l = len -1
    while(array[j] >= array[l]):
        l = l-1
    # print(f"After step 3 for l={l}, j={j} before swap {array}")
    array[j], array[l] = array[l], array[j]
    # print(f"After step 3 for l={l} j={j} after swap {array}")
    '''
    Reverse a[j+1...len-1](both inclusive)

    after reversing [1, 6, 2, 3, 4, 5]
    '''
    array[j+1:len] = reversed(array[j+1:len])
    # print(f"After step 4 reversing {array}")
    return True

array = [1,2,4,4,5]
array.sort()
len = len(array)
count =1
print(array)
'''
The algorithm visits every permutation in lexicographic order
generating one by one
'''
while(hasNextPermutation(array, len)):
    print(array)
    count = count +1
# The number of permutations will be n! if no duplicates are present, else less than that
# [1,4,3,3,2] -> 5!/2!=60
print(f"Number of permutations: {count}")

功能性风格

def addperm(x,l):
    return [ l[0:i] + [x] + l[i:]  for i in range(len(l)+1) ]

def perm(l):
    if len(l) == 0:
        return [[]]
    return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]

print perm([ i for i in range(3)])

结果：

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

我的Python解决方案：

def permutes(input,offset):
    if( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )

from typing import List
import time, random

def measure_time(func):
    def wrapper_time(*args, **kwargs):
        start_time = time.perf_counter()
        res = func(*args, **kwargs)
        end_time = time.perf_counter()
        return res, end_time - start_time

    return wrapper_time


class Solution:
    def permute(self, nums: List[int], method: int = 1) -> List[List[int]]:
        perms = []
        perm = []
        if method == 1:
            _, time_perm = self._permute_recur(nums, 0, len(nums) - 1, perms)
        elif method == 2:
            _, time_perm = self._permute_recur_agian(nums, perm, perms)
            print(perm)
        return perms, time_perm

    @measure_time
    def _permute_recur(self, nums: List[int], l: int, r: int, perms: List[List[int]]):
        # base case
        if l == r:
            perms.append(nums.copy())

        for i in range(l, r + 1):
            nums[l], nums[i] = nums[i], nums[l]
            self._permute_recur(nums, l + 1, r , perms)
            nums[l], nums[i] = nums[i], nums[l]

    @measure_time
    def _permute_recur_agian(self, nums: List[int], perm: List[int], perms_list: List[List[int]]):
        """
        The idea is similar to nestedForLoops visualized as a recursion tree.
        """
        if nums:
            for i in range(len(nums)):
                # perm.append(nums[i])  mistake, perm will be filled with all nums's elements.
                # Method1 perm_copy = copy.deepcopy(perm)
                # Method2 add in the parameter list using + (not in place)
                # caveat: list.append is in-place , which is useful for operating on global element perms_list
                # Note that:
                # perms_list pass by reference. shallow copy
                # perm + [nums[i]] pass by value instead of reference.
                self._permute_recur_agian(nums[:i] + nums[i+1:], perm + [nums[i]], perms_list)
        else:
            # Arrive at the last loop, i.e. leaf of the recursion tree.
            perms_list.append(perm)



if __name__ == "__main__":
    array = [random.randint(-10, 10) for _ in range(3)]
    sol = Solution()
    # perms, time_perm = sol.permute(array, 1)
    perms2, time_perm2 = sol.permute(array, 2)
    print(perms2)
    # print(perms, perms2)
    # print(time_perm, time_perm2)
```

这是受Haskell实现使用列表理解的启发：

def permutation(list):
    if len(list) == 0:
        return [[]]
    else:
        return [[x] + ys for x in list for ys in permutation(delete(list, x))]

def delete(list, item):
    lc = list[:]
    lc.remove(item)
    return lc