排列与组合

蔚落 2022-03-26 12:00 272阅读 0赞

# 排列与组合 #

### 文章目录 ###

*  排列与组合
 *   *  前言
     *  方法1
     *  方法2

## 前言 ##

诚然，排列组合作为高考数学里的送分题，它的出现让我这样的弱鸡一度欢喜。地处中央，上承“选择填空”，下启“数列圆锥”，紧绷的神经在这里可以微微松懈。

我依然记得排列公式是 A n m = n ! ( n − m ) ! A\_\{n\}^\{m\}= \\frac\{n!\}\{(n-m)!\} Anm=(n−m)!n!，而组合是 C n m = n ! m ! ∗ ( n − m ) ! C\_\{n\}^\{m\} = \\frac\{n!\}\{ m! \* (n-m)!\} Cnm=m!∗(n−m)!n!。

那么对于计算机来说，要怎样才实现排列组合呢？Python告诉你。

## 方法1 ##

作为“调包仔”的Python工程师不得不告诉你，有什么难题别立马想算法，要去想有没有现成的包。关于排列与组合嘿，还真有！

下面我以 A 3 2 A\_\{3\}^\{2\} A32和 C 3 2 C\_\{3\}^\{2\} C32举例说明——

计算排列组合结果的函数：

from scipy import special
    
    permResult = special.perm(3, 2)  # 排列结果
    
    combResult = special.comb(3, 2)  # 组合结果
    
    print("排列结果：", permResult)
    print("组合结果：", combResult)
    # 输出：
    排列结果： 6.0
    组合结果： 3.0

得到排列组合细节的函数：

from itertools import permutations, combinations
    
    permDetil = list(permutations(["a", "b", "c"], 2))  # 排列
    
    combDetil = list(combinations(["a", "b", "c"], 2)) # 组合
    
    print("排列详情：", permDetil)
    print("组合详情：", combDetil)
    # 输出：
    排列详情： [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
    组合详情： [('a', 'b'), ('a', 'c'), ('b', 'c')]

可以看出，排列与组合的区别在于：**排列需要关注顺序**，所以（a, b）与（b, a）算俩；**组合不用关注顺序**。

## 方法2 ##

直接调包很省事儿，但不酷。事实上，利用递归+迭代，我们也可以实现排列组合。

排列：

import copy
    
    results = []
    def permutations(lyst, num, result):
        if len(result) == num:
            results.append(result)
            return
        elif len(result) > num:
            return
        else:
            for i, __ in enumerate(lyst):
                newLyst = copy.copy(lyst)
                newResult = copy.copy(result)
                newResult.append(newLyst.pop(i))
                
                permutations(newLyst, num, newResult)  # 递归
                
    permutations(["a", "b", "c"], 2, [])
    print(results)
    # 输出：
    [['a', 'b'], ['a', 'c'], ['b', 'a'], ['b', 'c'], ['c', 'a'], ['c', 'b']]

组合：

import copy
    
    results = []
    def permutations(lyst, num, result):
        if len(result) == num:
            results.append(result)
            return
        elif len(result) > num:
            return
        else:
            for i, __ in enumerate(lyst):
                newLyst = copy.copy(lyst)
                newResult = copy.copy(result)
                newResult.append(newLyst.pop(i))
                
                permutations(newLyst[i:], num, newResult)  # 排列与组合的区别在这里
                
    permutations(["a", "b", "c"], 2, [])
    print(results)
    # 输出：
    [['a', 'b'], ['a', 'c'], ['b', 'c']]

关于递归思想这里不做讲解，可参看我的另一文[浅谈递归思想][Link 1]。

[Link 1]: http://youguanxinqing.xyz/index.php/archives/27/