排列与组合

数学基础 2019-01-16 2549 字 22 浏览 点赞

前言

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

我依然记得排列公式是,而组合是

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

方法1

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

下面我以举例说明——

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

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']]

关于递归思想这里不做讲解,可参看我的另一文:浅谈递归思想



本文由 Guan 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论