排列组合怎么算(排列组合算法真的很厉害)

要求

最近我在工作中遇到一个要求:我们的数据表有多个维度，多个维度的任意组合都可能导致一些“奇妙”的反应。因为我不确定如何组合它们，所以我需要列出所有的组合来尝试。

抽象就是从一个集合中取出任意元素，形成唯一的组合。比如【a，b，c】可以组合成【a】，【b】，【c】，【ab】，【bc】，【ac】，【abc】。

要求如下:

组合中的元素数大于0且小于或等于数组大小；

组合中不能有重复的元素，比如【aab】就是不合格的组合；

组合中元素的位置是任意的，即[ab]和[ba]视为同一个组合；

看到这里，你应该会想到高中学过的排列组合。这与从一个集合中取出元素来形成另一个集合是一样的。如果一个集合中的元素是随机的，它就是一个组合。有一些元素A和元素B的组合。而如果要求元素的顺序不同，视为不同的集合，那就是置换。从M个元素到N个元素有几种排列。

我满足的这个要求是一个典型的组合，用一个公式表示，就是从一个有n个元素的集合中列出一个组合。

该算法用Java实现。

从排列到组合-详尽无遗

对于这种需求，首先想到的当然是穷举。因为排列要求少，所以比较容易实现。如果我先把所有的安排搞清楚，再剔除因为位置不同而重复的元素，就能实现要求了。假设所有的组合都需要从[A B C D E]的五行中取出，那么我们就可以先找出所有元素的完整排列，再去掉像[A B]和[B A]这两个集合的权重。

我们也知道，所以先考虑一个情况。假设从五个元素中选取三个元素进行全排列。

所选择的三个元素中的每一个都可以是ABCDE中的一个，然后如果在形成的集合中有重复的元素，则它是5中3的完整排列。

代码是这样的:

对于结果组合，我借用了Java中HashSet的两个特性:

元素的唯一性，选择三个元素放入集合中，重复的会被过滤掉，所以可以通过集合的大小来判断是否有重复的元素。

元素无序，集合[A B]和集合[B A]都表示为集合[A B]。此外，由于元素的唯一性，将只保留表示为Set[A B]的多个集合中的一个，这有助于将整个排列变成组合。可以注意到，上面程序中的count参数是写死的。如果需要取出四个元素，就需要四层循环嵌套。如果选择的元素是可变的，那么普通的编码方法就不合适。

注意:具有可变层的循环可以通过递归实现。

从排列到组合——分而治之

疲惫，毕竟太暴力了。让我们通过分而治之的思想来重新考虑这个问题:

分而治之思想

一般来说，分而治之的思想是“逆来顺受，逆来顺受”。它把复杂的问题分成简单的，直到可以直接求解，然后从这个直接可解的问题向上聚合，最终解决问题。

从M个元素中提取N个元素的整个问题非常复杂，可以理解为:

首先，如果我们已经从M中的元素中取出了一个元素，那么集合中还剩下M-1个元素，只剩下N-1个元素需要取出。如果不好解，我们假设从M-1中取出另一个元素，集合中还剩下M-2个元素，只需要取N-2个元素。直到我们可能取M-N+1次，只剩下一个元素要取，然后从剩下的集合中取就是一个简单的问题了。很简单，有M-N+1种取数方法。如果解决了这个问题，我们已经取完了最后一次，产生了M-N+1个临时集，再考虑从M-N+2个元素中取一个元素。也有M-N+2种可能。这些可能性聚合在一起，直到得到n个元素，问题就解决了。

或者从5个元素中取出3个元素的例子:

从五行中选择三种元素是一个复杂的问题。为了简化，我们认为去掉了一个元素，剩下的四个元素还要再去掉两个元素。求解公式为:。要解决取出四个元素中的两个仍然不容易，所以我们假设取出另一个元素。接下来的问题是如何取三个元素中的一个。公式是。从三个元素中选一个已经是很简单的问题了。有三种可能，然后再往上乘以四分之一和五分之一的可能性，就能解决这个问题。代码实现

用如下代码实现:

其实就是递归。

直接命中基本位操作

从元素的整体排列中寻找整体组合比穷举略好，但不是最好的方法。毕竟它“走了一次弯路”。

很多算法都可以通过位运算秒级求解，其优点主要有两个:一是位运算在计算机中效率高，二是因为位运算语义简单，所以大部分算法都直指本质。

组合算法也可以通过位运算来实现。

想

再次考虑全组合的要求，从M个元素中任意选择一个元素组成组合。组合中的元素不能重复，元素的位置无关紧要。

之前的方法都是从结果组合是否满足要求，组合是否有重复元素，相同的组合是否已经存在等等来考虑问题。如果换个思路，从要选的元素来考虑呢？

对于每个元素，它的状态要简单得多，要么放入组合，要么不放入。每个元素都有这两种状态。如果从五个元素中随机选取N个元素组成一个组合，则用二进制位表示每个元素是否放入该组合，即:

看到这里，应该很清楚，每个组合都可以分解成N个二进制数的表达式，每个二进制组合同时代表一个十进制数，所以每个十进制数都可以代表一个组合。

我们可以很容易地计算出十进制数的个数，从00000开始…到11111…各种都有，排除不全部放入组合的可能，结果也有各种。