Python实现数组的全排列

全排列的定义

  1.     **全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。**<br />
  2.     **公式：全排列数f(n)=n!(定义0!=1)，如1,2,3三个元素的全排列为：**<br />

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
共3_2_1=6种。

    对于上述例子，我们可以采用for循环的方法进行实现。

    方法一：采用for循环

def func(nums):
    dp = []     # 存储所有可能的排列组合
    res = []        # 存储单个排列
    for i in nums:
        res.append(i)       # 添加第一个元素
        for j in nums:
            if j not in res:        # 判断元素是否存在
                res.append(j)
                for k in nums:
                    if k not in res:        # 判断元素是否存在
                        res.append(k)       # 生成可能的排列
                        dp.append(res)        # 存储排列
            res = res[:1]       # 第一个元素不变，尝试其他可能
        res = []        # 全部重新排列
    return dp

print(func([1,2,3]))

    运行结果：

[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]

    利用for循环方法生成所有排序的可能，在上面生成三个元素的全排列时就要利用三层for循环，如果要生成更多元素的全排列就需要更多的for循环，这会大大增加代码的时间复杂度，并且代码量也会增大。那么是否有更好的方法呢？

    方法二：导入itertools模块的permutations方法

from itertools import permutations

def func(iterable):
    return list(permutations(iterable))

print(func(iterable=['1','2','3']))

    此方法采用Python的itertools模块中的permutations方法。

itertools模块中生成排列组合的四种方法

1.product()

    **返回可迭代项的笛卡尔积。**<br />
    **调用方法：itertools.product(_ iterables，repeat = 1)。_<br />
    **其中_iterables表示可迭代项，可以有多项；repeat表示元素的重复次数，可以进行指定(repeat=0时，返回一个空元组)，默认值为1。_

    代码实现：

from itertools import product

def func(arr1, arr2):
    return list(product(arr1, arr2, repeat=1))

print(func(['A', 'B', 'C', 'D'], ['x', 'y']))

    运行结果：

[('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y'), ('D', 'x'), ('D', 'y')]

    上述的itertools.product()方法其实就等价于下面的嵌套for循环方法。

def product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

2.permutations()

    **返回可迭代项的元素的连续r长度排列（所有可能的顺序组合，没有重复的元素）。**<br />
    **调用方法：itertools.permutations(iterable, r=None)。**<br />
    **其中iterable表示可迭代项，只有一项； r代表每个序列的长度，默认值为可迭代项的长度(即默认生成可迭代项的全排列)，可以进行指定(r=0时，返回一个空元组)。**

    代码实现：

from itertools import permutations

def func(iterable):
    return list(permutations(iterable, r=2))   # 此处我们指定生成两项的组合

print(func(iterable=['1','2','3']))

    运行结果：

[('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]

3.combinations()

    **返回可迭代项的元素的连续r长度排列（按排序顺序，无重复元素）。**<br />
    **调用方法：itertools.combinations(iterable, r)。**<br />
    **其中iterable表示可迭代项，只有一项； r代表每个序列的长度，需要进行指定(当r=0时，返回一个空元组；当r>len(iterable)时，返回None)。**

    代码实现:

from itertools import combinations

def func(iterable):
    return list(combinations(iterable, r=2))

print(func([1,2,3,4]))

    运行结果：

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

4.combinations_with_replacement()

    **返回可迭代项的元素的连续r长度排列（按排序顺序，带有重复的元素），允许单个元素重复多次（元素重复次数<=r）。**<br />
    **调用方法：itertools.combinations_with_replacement(iterable, r)。**<br />
    **其中iterable表示可迭代项，只有一项； r代表每个序列的长度，需要进行指定(r=0时，返回一个空元组)。**

    代码实现:

from itertools import combinations_with_replacement

def func(iterable):
    return list(combinations_with_replacement(iterable, r=3))

print(func([1,2,3]))

    运行结果：

[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

itertool模块使用手册：https://docs.python.org/3.7/library/itertools.html