def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

输出：['abc'，'acb'，'bac'，'bca'，'cab'，'cba']

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

注意，该算法具有n个阶乘时间复杂度，其中n是输入列表的长度

打印跑步结果：

global result
result = [] 

def permutation(li):
if li == [] or li == None:
    return

if len(li) == 1:
    result.append(li[0])
    print result
    result.pop()
    return

for i in range(0,len(li)):
    result.append(li[i])
    permutation(li[:i] + li[i+1:])
    result.pop()    

例子：

permutation([1,2,3])

输出：

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

from __future__ import print_function

def perm(n):
    p = []
    for i in range(0,n+1):
        p.append(i)
    while True:
        for i in range(1,n+1):
            print(p[i], end=' ')
        print("")
        i = n - 1
        found = 0
        while (not found and i>0):
            if p[i]<p[i+1]:
                found = 1
            else:
                i = i - 1
        k = n
        while p[i]>p[k]:
            k = k - 1
        aux = p[i]
        p[i] = p[k]
        p[k] = aux
        for j in range(1,(n-i)/2+1):
            aux = p[i+j]
            p[i+j] = p[n-j+1]
            p[n-j+1] = aux
        if not found:
            break

perm(5)

递归之美：

>>> import copy
>>> def perm(prefix,rest):
...      for e in rest:
...              new_rest=copy.copy(rest)
...              new_prefix=copy.copy(prefix)
...              new_prefix.append(e)
...              new_rest.remove(e)
...              if len(new_rest) == 0:
...                      print new_prefix + new_rest
...                      continue
...              perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']

生成所有可能的排列

我正在使用python3.4：

def calcperm(arr, size):
    result = set([()])
    for dummy_idx in range(size):
        temp = set()
        for dummy_lst in result:
            for dummy_outcome in arr:
                if dummy_outcome not in dummy_lst:
                    new_seq = list(dummy_lst)
                    new_seq.append(dummy_outcome)
                    temp.add(tuple(new_seq))
        result = temp
    return result

测试用例：

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)