#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

输出：

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

当我交换列表的内容时，需要一个可变的序列类型作为输入。例如，烫发（list（“ball”）会起作用，而烫发（“ball”）不会起作用，因为你不能更改字符串。

这种Python实现的灵感来自Horowitz、Sahni和Rajasekeran在《计算机算法》一书中提出的算法。

另一种解决方案：

def permutation(flag, k =1 ):
    N = len(flag)
    for i in xrange(0, N):
        if flag[i] != 0:
            continue
        flag[i] = k 
        if k == N:
            print flag
        permutation(flag, k+1)
        flag[i] = 0

permutation([0, 0, 0])

此解决方案实现了一个生成器，以避免在内存中保留所有排列：

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto

如果用户希望在列表中保留所有排列，可以使用以下代码：

def get_permutations(nums, p_list=[], temp_items=[]):
    if not nums:
        return
    elif len(nums) == 1:
        new_items = temp_items+[nums[0]]
        p_list.append(new_items)
        return
    else:
        for i in range(len(nums)):
            temp_nums = nums[:i]+nums[i+1:]
            new_temp_items = temp_items + [nums[i]]
            get_permutations(temp_nums, p_list, new_temp_items)

nums = [1,2,3]
p_list = []

get_permutations(nums, p_list)

以下代码是给定列表的就地排列，作为生成器实现。由于它只返回对列表的引用，因此不应在生成器外部修改列表。该解决方案是非递归的，因此使用了低内存。还可以很好地处理输入列表中元素的多个副本。

def permute_in_place(a):
    a.sort()
    yield list(a)

    if len(a) <= 1:
        return

    first = 0
    last = len(a)
    while 1:
        i = last - 1

        while 1:
            i = i - 1
            if a[i] < a[i+1]:
                j = last - 1
                while not (a[i] < a[j]):
                    j = j - 1
                a[i], a[j] = a[j], a[i] # swap the values
                r = a[i+1:last]
                r.reverse()
                a[i+1:last] = r
                yield list(a)
                break
            if i == first:
                a.reverse()
                return

if __name__ == '__main__':
    for n in range(5):
        for a in permute_in_place(range(1, n+1)):
            print a
        print

    for a in permute_in_place([0, 0, 1, 1, 1]):
        print a
    print

这是初始排序后生成排列的渐近最优方式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}")