Python组合学

从2.2版开始，标准python库提供了许多用于生成组合对象的工具，但我在Internet上找不到一篇文章详细讨论如何使用它们。 因此，我决定纠正这一遗漏。

首先，我将讨论组合技术及其基本公式。 如果您已经熟悉数学的这一部分，则可以跳过这些段落。

假设我们有一个由n个不同字母组成的字符串，并且我们想计算所有重新排列这些字母的方式，以便获得新的一行。 对于该行的第一个位置，我们可以选择拥有的n个字母之一，对于第二个位置，可以选择n - 1个字母之一，依此类推。 结果，我们得到乘积n （n-1） ... * 1 = n！ 不重复的n个元素的排列数目 。

现在想象一下，字符串中字母的数量是有限的。 我们有n个字母可用，并且我们想计算从中得到长度为k的字符串的方法的数量，其中k <n，每个字母只能使用一次。 然后我们可以将n个字母之一放在该行的第一个位置，将n-1个字母之一放在第二个位置，将n-k + 1个字母之一放在第k个位置。 行的总数将等于n （n-1） （n-2） ... （n-k + 2） （n-k + 1）= n！/（Nk）！ 从n到k的展示位置数量 。 如果不需要字母的唯一性，则可以得到公式n ... n n = n ^ k ，其中n到k个重复的位置数 。

在此之前，我们对顺序进行了排序，并考虑了元素的顺序，以及顺序对我们而言无关紧要怎么办。 例如，我们有n个不同的糖果，我们想从它们中选择k个给朋友，k <n。 有多少种方法可以从n个中选择k个糖果而无需考虑顺序？ 答案很简单，一开始我们会发现n×k的位置没有重复，但是随后将重复序列顺序不同的相同糖果。 有多少种方法可以重新排列k个糖果？ 没错，没有重复的k个元素的排列。 最终的答案：n乘以k的位置除以k的排列而无重复。 配方 $$$n！/（n-k）！/ k！$n×k的组合数 。

考虑到情况更复杂，我们有n个盒子，每个盒子包含许多口味相同的糖果，但是在不同的盒子中口味不同。 有多少种方法可以从k个糖果中送礼物给朋友，并且相同的味道会出现多少次？ 由于顺序对我们而言无关紧要，因此，请按以下顺序排列礼品糖果：首先，将依次出现第一个口味的糖果，然后是第二个口味的糖果，依此类推，如果礼物中没有任何口味的糖果，我们将在不同口味的糖果之间进行匹配-那些本应在左右两侧限制这种口味的比赛将并排站立。 此外，由于只有n种口味，所以我们得到了一个由k个糖果和n-1个匹配项组成的序列，并用匹配项将它们分开。 现在请注意，通过匹配的位置，我们可以恢复原始集合。 那么答案将是在不考虑顺序的情况下将n-1个匹配项放置在n + k-1单元中的方法的数量，该顺序等于n + k-1与n-1的组合的数量，公式为： $$$（n + k-1）！/ k！/（n-1）！$n到k重复的组合数 。

现在，我们将在组合学上考虑几个问题，以巩固材料。

任务1

有20个人，有多少种配对方法
解决方案：以第一人称，有多少种方法可以为他选择一对： $$$20-1 = 19$，请选择第二个人，有多少种方法可以为他选择一对： $$$20-2-1 = 17$。 答案：19！ = 654729075

任务2

有10个男人和10个女孩，有多少种方法可以将他们分解成由相同数目的男人和女孩组成的公司，所以不考虑一个空公司
解决方案：
方法1：由一个男人和一个女孩组建公司的方式数量等于选择一个女孩的方式数量和选择一个男人的方式数量的乘积。 从10个女孩中选择一个女孩的方法的数量等于10：1的组合（不重复），与男人相似，因此我们将进行平方。 接下来，我们类似地计算10到2的组合，从10到3，依此类推，直到10到10的组合。最终公式为： $$$（10！/（10-1）！/ 1！）^ 2 +（10！/（10-2）！/ 2！）^ 2 + ... +（10！/（10-10）！/ 10！）^ 2$。
方法2：考虑在公司中有很多男人，在公司中没有很多女孩。 对于此集合，您绝对可以恢复公司，并且公司中的人数始终等于10，因为 $$$k +（10-k）= 10$，k-公司中的人数， $$$10-k$-不包括在内的女孩​​人数。 这样的集合的数量等于20到10的组合的数量，在最后的答案中，我们还将减去一个，以便当我们的集合中有10个女孩时不考虑空公司。 最终公式： $$$20！/（20-10）！/ 10！ -1 = $ 18475$。

因此，我们了解了理论，现在我们将学习如何使用标准python库生成组合对象。
我们将使用itertools库

from itertools import * 

使用置换功能，可以为可迭代对象生成所有置换。

例子1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba 

基于第二个调用，我们注意到在不同位置的相同元素被认为是不同的。

例子2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb 

放置与排列的区别在于可用单元数的限制

例子3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc 

使用重复布局，您可以轻松地遍历由给定字符组成的所有定长字符串

例子4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd 

使用无重复的组合，您可以遍历给定字符串，数组或其他可迭代对象中的所有非重复字母集，而无需考虑顺序

例子5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd 

结果类似于调用组合 ，但是具有相同元素的集合也将添加到结果中。

材料：
N.V. 戈尔巴乔夫“数学奥林匹克题集”
俄语Python文档