Python - 数据结构与算法之排列与组合

发布时间：2024年01月02日

一.引言

二.排列 A-Permute

一.引言

关于排列前面已经介绍了一部分算法，例如求数组的全排列，求子集等等，我们可以使用回朔的方法进行计算，今天主要讲下数学上排列与组合的计算方式，因为有一些题目可以巧妙地使用排列组合快速得到结果，下面整理下定义与 Python 实现方式。

二.排列 A-Permute

◆ 定义

排列公式采用如下形式:

????????????????????????? $A_{6}^{2}$ ?

其中 6、2 代表从 6 个元素里面选 2 个排列起来，注意这一要求有顺序 !

丽茹从 1-6 中选 2 个数字组成两位数，这个结果就是 A(6, 2)

又丽茹从 1-6 编号的同学中，一个当数学课代表，一个当语文课代表，那结果也是 A(6, 2)

◆ 计算

这是百度百科关于排列的定义和计算公式，下面我们简化下流程方便记忆:

$A_{6}^{2} = \frac{6!}{6-2=4!} = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 }{4 \cdot 3 \cdot 2 \cdot 1 } = 6 \cdot 5$

有一个好记的方法，只要 A(m, n) 出来，我们就从 m! 开始往后写，写到第 n 个数字停止即可。例如 A(5, 3) 我们从 5 开始往后写 3 个数字即 5x4x3，ok 搞定了!

Tips:

如果从实际含义理解的话这是个无放回的问题，6 个里面选 2 个，第一次我们选一个人出来有 6 种可能，由于不能重复，所以现在还剩 5 个人，我们再从 5 个人里面随便抓一个出来就凑齐 2 个人了，所以是 6 x 5。

◆ 性质

$A_n^{n} = n! = n \cdot \ (n-1) \cdots 2 \cdot 1$

◆ 实现

def factorial(num):
    """计算阶乘"""
    result = 1
    for i in range(1, num + 1):
        result *= i
    return result

def permutation(m, n):
    """计算排列 A(m, n)"""
    return factorial(m) // factorial(m-n)

计算两个阶乘相除即可，当然按照我们红色字体部分，我们可以快速计算，避免 (m-n)！的重复计算。

def fast_permutation(m, n):
    if m == 1:
        return 1

    # 从 m 开始往后乘 n 次完活
    re = 1
    for i in range(n):
        re *= m
        m -= 1

    return re

三.组合 C-Combine

◆ 定义

组合公式采用如下形式:

????????????????????????? $C_{6}^{2}$ ?

其中 6、2 代表从 6 个元素里面选 2 个组合起来，注意这里 无顺序 !?

丽茹从 1-6 中选 2 个数字，这个结果就是 C(6, 2)

又丽茹从 1-6 编号的同学中选两个打扫卫生，那结果也是 C(6, 2)

◆ 计算

还是先把长长的公式掏出来，下面我们简化下流程方便记忆:?

$C_{6}^{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(2 \cdot 1) \cdot (4\cdot 3\cdot 2\cdot 1)} = \frac{6\cdot 5}{1\cdot 2}$

有一个好记的方法，对于给定的 m、n，分母 m 从大往小写 n 个，分子从 1 到 n 写下来 。例如 C(6, 2) 直接 6 从大到小写 2 个即 6x5，再从 1写到 n，即 1x2，除去吧，一除一个不知道。

Tips:

继续从实际情况下理解一下，首先这里还是无放回的问题，我们第一次能够取 m 个，下一次能取 m-1 个，依次类推。以 (3, 2) 为例，我们可以取 (1, 2) (1, 3)、(2,1) (2,3)、(3,1),(3,2)，2个数字的组合 (1,2)、(2,1) 是一样的，所以我们重复了，重复了多少次就和 n 有关系了，n 能够排列 n! 种组合，所以就是 3 * (3-1) 直到 n 也就是 3 * 2，重复的话是 2! = 2 * 1，所以一共就 3 种组合 (1, 2)、(1、3)、(2, 3)。即 A(m, n) / n!

◆ 性质

若 a+b = n 则存在以下关系，这个可以逆向思维理解一下，这里就不多解释了:

$C_n^{a} = C_n^{b}$

根据公式也可以推导出特殊情况:

$C_n^{0} = C_n^{n} = 1$

◆ 实现

def factorial(num):
    """计算阶乘"""
    result = 1
    for i in range(1, num + 1):
        result *= i
    return result

def combination(m, n):
    """计算排列 A(m, n)"""
    return factorial(m) // factorial(m-n) // factorial(n)

套公式的话按上面的方法写，也可以用我们红字的快速计算方法，避免重复计算。按照这个公式直接套用即可?C(m, n) = A(m, n) / n!

def fast_combination(m, n):
    if m == 1:
        return 1

    re = 1
    for i in range(n):
        re *= m
        m -= 1

    return re // factorial(n)

四.经典算法题目

下面四个题目来自:?Python - Divide Conquer 分治 & Backtrack 回朔

1.全排列 [无重复]

全排列[无重复]:?https://leetcode-cn.com/problems/permutations/

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        re = []

        def dfs(position):
            if position == len(nums) - 1:
                re.append(nums[:])

            # 固定第一个位置，再寻找下一个位置，循环
            for i in range(position, len(nums)):
                nums[position], nums[i] = nums[i], nums[position]
                dfs(position + 1)
                nums[position], nums[i] = nums[i], nums[position]

        dfs(0)

        return re

这里 for i in range(position, len(nums)) 就是一个不断逼近的过程，就像 A(m,m) 一样，第一次有 m 个选择，下一次有 m-1 个选择，一直循环到最后一个数字。

上面这版交换索引不好理解的话，就用我们全排列的思想，固定第一个无放回，从剩下的找，这里无放回的操作我们使用 set，用过的就放到 set 不能用了：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        re = []

        def dfs(cur, used):
            if len(cur) == len(nums):
                re.append(cur[:])

            for i in range(0, len(nums)):
                if nums[i] in used:
                    continue
                # 下一层进发
                cur.append(nums[i])
                used.add(nums[i])
                dfs(cur, used)
                # 恢复状态
                cur.pop()
                used.remove(nums[i])

        used = set()
        dfs([], used)

        return re

2.全排列 [有重复]

全排列[有重复]:?https://leetcode.cn/problems/permutations-ii/

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        re = []

        def dfs(position):

            if position == len(nums) - 1:
                re.append(nums[:])

            repeat = set()

            for i in range(position, len(nums)):
                if nums[i] in repeat:
                    continue
                repeat.add(nums[i])

                nums[position], nums[i] = nums[i], nums[position]
                dfs(position + 1)
                nums[position], nums[i] = nums[i], nums[position]

        dfs(0)

        return re

固定第一个位置，固定第二个位置依次类推，这里变换位置时，如果有重复就不再变换了，排除这次的结果。

同理，我们可以使用人脑思维，即固定一个，再找剩下的不过同理需要进行去重操作:

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        re = []

        def dfs(cur, used):
            if len(cur) == len(nums):
                re.append(cur[:])

            repeat = set()

            for i in range(0, len(nums)):
                # 当前索引用过了 或者 当前元素重复了
                if i in used or nums[i] in repeat:
                    continue

                repeat.add(nums[i])

                # 下一层进发
                cur.append(nums[i])
                used.add(i)
                dfs(cur, used)
                # 恢复状态
                cur.pop()
                used.remove(i)

        used = set()
        dfs([], used)

        return re

加了两个 set 没想到效率就是不一样。

3.组合 [可重复]

组合:?https://leetcode.cn/problems/combinations/description/

class Solution(object):
    def combine(self, n, k):
        res = []
        
        def dfs(cur, position):

            if len(cur) == k:
                res.append(cur[:])
                return 
            
            for i in range(position, n):
                cur.append(i + 1)
                dfs(cur, i + 1)
                cur.pop()

        dfs([], 0)

        return res

[0, 1, 2, 3] 固定 0，再去找 123 组合、再固定 1 去找 23 组合，直到最后结束。?

4.子集 [无重复]

子集:?https://leetcode.cn/problems/subsets/description/

class Solution(object):

    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        # 遍历每个数字
        for i in nums:
            res = res + [[i] + re for re in res]
        return res

不断累加 res 的值，最终得到全部的子集结果。当然这个题其实可以用组合来配合，因为全部的子集就是 C(n,i) for i in range(0, n+1) 的结果，我们可以执行合并操作。

换递归的实现操作下:

class Solution(object):

    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        res = []    
        n = len(nums)

        def dfs(position, cur):
            res.append(cur)
            for i in range(position, n):
                dfs(i + 1, cur + [nums[i]])

        dfs(0, [])
        return res

上图可以方便大家理解本题，相当于 1 和后面的 2、3 组合，1，2 和后面的 3 组合，1 和 3 组合以此类推。

5.子集 [有重复]

子集:?https://leetcode.cn/problems/subsets-ii/

class Solution(object):

    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        res = []
        n = len(nums)
        nums.sort()

        def dfs(position, cur):
            res.append(cur)
            uset = set()
            for i in range(position, n):
                if nums[i] in uset:
                    continue
                uset.add(nums[i])
                dfs(i + 1, cur + [nums[i]])

        dfs(0, [])
        return res

?在前面求子集的基础上增加了 repeat 判重。

五.总结

上面整理了排列组合的相关定义与公式，并在下面实现了几种常见的排列组合算法，这几个算法大家可以熟练掌握，应为很多问题的解决都可以使用这些方法直接简化我们的流程，同时一些路径的问题使用排列组合公式可以直接出答案，非常的方便。

Tips:

上面的代码解析在?分治与回溯?的章节里有详细的注释和分析过程。

文章来源:https://blog.csdn.net/BIT_666/article/details/135295819
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

Python - 数据结构与算法之 排列与组合

一.引言

二.排列 A-Permute

◆ 定义

◆ 计算

◆ 性质

◆ 实现

三.组合 C-Combine

◆ 定义

◆ 计算

◆ 性质

◆ 实现

四.经典算法题目

1.全排列 [无重复]

2.全排列 [有重复]

3.组合 [可重复]

4.子集 [无重复]

5.子集 [有重复]

五.总结

Python - 数据结构与算法之排列与组合