排列组合在编程中很经常会用到，出于好奇，翻里一下python函数库中的排列和组合的函数，觉得写得挺巧妙得，对比自己写的，还是有点值得学习的地方。

itertools.permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def permutations(iterable, r=None):
    #'permutations(range(3), 2) --> (0,1) (0,2) (1,0) (1,2) (2,0) (2,1)'
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    indices = range(n)               # [0,1,2...] 索引,用于选择出排列
    cycles = range(n-r+1, n+1)[::-1] # [3,2]  确保循环次数为n！/(n-r)! -1，每次循环时候用于i与
    yield tuple(pool[i] for i in indices[:r]) # 取出前r个

    while n:
        for i in reversed(range(r)): # [...1,0],从cycles尾部开始循环
            cycles[i] -= 1
            print i, cycles[i], cycles,indices
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1] #把第i个索引放到最后
                cycles[i] = n - i #重置第i个循环标记
            else:
                j = cycles[i]  #j值相当于i+1,i+2,i+3......n-1，倒数第j个数
                indices[i], indices[-j] = indices[-j], indices[i] #前后换位
                print indices
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

代码执行逻辑

  1. 循环： 按照n！/(n-r)! 循环，从indices队尾部开始循环，indices[i]相当于倒数第n个数
  2. 移动：每次循环，把第i个数与i后面的数交换位置
    i与j互换的j位置等价于：
(i, n-i+1)
(i, n-i+2)
(i, n-i+3)
(i, .....)
(i, n-1)

    全部位置都缓过一次后，cycles[i] == 0，把第i个数放到最后面，这个时候indices的顺序和第一次换位前一致，这个算法巧妙之处

  3. 结束：当cycles所有数减到成0时候结束循环

执行过程描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 3选2排列输出
# ----------- for_loop 1 ------------
# i=1 v=1 cycles=[3, 1] indices=[0, 1, 2]
# [0, 2, 1]
# cycle位置1数值为1，indices 1与-1位置互换     [0, 1, 2] -> [0, 2, 1]
# 根据indices前两个下标取出pool数值组成排列

# ----------- for_loop 2 ------------
# i=1 v=0 cycles=[3, 0] indices=[0, 2, 1]
# i=0 v=2 cycles=[2, 2] indices=[0, 1, 2]
# [1, 0, 2]
# cycle位置1数值为0，把indices位置i=1的数放到最后 [0, 2, 1] -> [0, 1, 2], cycles[1] = 2
# cycle位置0数值为2，indices 0与-2位置互换       [0, 1, 2] -> [1, 0, 2]

# ----------- for_loop 3 ------------
# i=1 v=1 cycles=[2, 1] indices=[1, 0, 2]
# [1, 2, 0]
# cycle位置1数值为1，indices 1与-1位置互换      [1, 0, 2] -> [1, 2, 0]

# ----------- for_loop 4 ------------
# i=1 v=0 cycles=[2, 0] indices=[1, 2, 0]
# i=0 v=1 cycles=[1, 2] indices=[1, 0, 2]
# [2, 0, 1]
# cycle位置1数值为0，把indices位置i=1的数放到最后 [1, 2, 0] -> [1, 0, 2], cycles[1] = 2
# cycle位置0数值为1，indices 0与-1位置互换     [1, 0, 2] -> [2, 0, 1]

# ----------- for_loop 5 ------------i=
# i=1 v=1 cycles=[1, 1] indices=[2, 0, 1]
# [2, 1, 0]
# cycle位置1数值为1，indices 1与-1位置互换     [2, 0, 1] -> [2, 1, 0]

# ----------- for_loop 6 ------------
# i=1 v=0 cycles=[1, 0] indices=[2, 1, 0]
# i=0 v=0 cycles=[0, 2] indices=[2, 0, 1]
# 两次循环正常结束，跳到else的return结束循环

数组循环示意图

permutation_move.png

itertools.combinations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r) # [0,1,2...] 索引,用于选择组合
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)): #[...2,1,0]...
            if indices[i] != i + n - r: #indices为倒数r个的索引时候停止
                break
        else:
            return
        #此处i为上面beak时候的i
        print "i=%s"%i
        print "befor move: indices=%s, range=%s"%(indices, range(i+1, r))
        #把i后面的数组每次往数组后面推动移动1格
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1

        print "after move: indices=%s"%indices
        print "-" * 10
        yield tuple(pool[i] for i in indices)

代码执行逻辑

  1. 循环：按照选择个数r的倒序索引循环
  2. 移动：每次循环把 索引i中的位置+1，以及把i+往后的位置也移动一格
  3. 结束：当索引数组indices保存的位置全部刚好为倒数第r个时候停止

执行过程描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#6选3的输出
# i=2
# befor move: indices=[0, 1, 2], range=[]
# after move: indices=[0, 1, 3]
# ----------
# i=2
# befor move: indices=[0, 1, 3], range=[]
# after move: indices=[0, 1, 4]
# ----------
# i=2
# befor move: indices=[0, 1, 4], range=[]
# after move: indices=[0, 1, 5]
# ----------
# i=1
# befor move: indices=[0, 1, 5], range=[2]
# after move: indices=[0, 2, 3]
# ----------
# i=2
# befor move: indices=[0, 2, 3], range=[]
# after move: indices=[0, 2, 4]
# ----------
# i=2
# befor move: indices=[0, 2, 4], range=[]
# after move: indices=[0, 2, 5]
# ----------
# i=1
# befor move: indices=[0, 2, 5], range=[2]
# after move: indices=[0, 3, 4]
# ----------
# i=2
# befor move: indices=[0, 3, 4], range=[]
# after move: indices=[0, 3, 5]
# ----------
# i=1
# befor move: indices=[0, 3, 5], range=[2]
# after move: indices=[0, 4, 5]
# ----------
# i=0
# befor move: indices=[0, 4, 5], range=[1, 2]
# after move: indices=[1, 2, 3]
# ----------
# i=2
# befor move: indices=[1, 2, 3], range=[]
# after move: indices=[1, 2, 4]
# ----------
# i=2
# befor move: indices=[1, 2, 4], range=[]
# after move: indices=[1, 2, 5]
# ----------
# i=1
# befor move: indices=[1, 2, 5], range=[2]
# after move: indices=[1, 3, 4]
# ----------
# i=2
# befor move: indices=[1, 3, 4], range=[]
# after move: indices=[1, 3, 5]
# ----------
# i=1
# befor move: indices=[1, 3, 5], range=[2]
# after move: indices=[1, 4, 5]
# ----------
# i=0
# befor move: indices=[1, 4, 5], range=[1, 2]
# after move: indices=[2, 3, 4]
# ----------
# i=2
# befor move: indices=[2, 3, 4], range=[]
# after move: indices=[2, 3, 5]
# ----------
# i=1
# befor move: indices=[2, 3, 5], range=[2]
# after move: indices=[2, 4, 5]
# ----------
# i=0
# befor move: indices=[2, 4, 5], range=[1, 2]
# after move: indices=[3, 4, 5]

数组移动示意图

combinations_move.png

自己写的排列组合

自己写的感觉容易理解些，排列的性能对比函数库的性能差别不是很大，组合的性能相差较大，主要在数组复制和切割操作多了。
排列 

1
2
3
4
5
6
7
8
9
10
11
12
13
def permutations2(nums, n = None, index = 0):
    if not n:
        n = len(nums)

    if index == n:
        yield tuple(nums[:n])
        return

    for i in range(index, len(nums)):
        nums[index],nums[i] = nums[i],nums[index]
        for x in permutations2(nums, n, index+1):
            yield x
        nums[i],nums[index] = nums[index],nums[i]

组合 

1
2
3
4
5
6
7
8
9
10
11
12
13
def combinations2(nums, n, result = None):
    if not result:
        result = []

    if len(result) == n:
        yield tuple(result)
        return

    for i in range(len(nums)):
        result1 = result[:]
        result1.append(nums[i])
        for x in combinations2(nums[i+1:], n, result1):
            yield x

性能对比

性能优化主要更具leetcode上面的排列组合的练习题测试，获得一个大概相对的效率（在几十ms的效率时候，分别提交多次代码检测出的性能变化也可能较大），图片中的性能上面的性能为库函数，下面的的是自己写的。

排列练习题
组合练习题

排列
permutations_leetcode_perfermence.png
组合
combinations_leetcode_perfermence.png

else:

从python源代码中还看到了一种之前很少用到的语法，
for … in :
…
else:
…
在for in循环中判断条件然后break执行逻辑然后全部循环完了再else跳出，有趣！