最近工作中碰到一个需求：我们的数据表有多个维度，任意多个维度组合后进行groupby可能会产生一些”奇妙”的反应，由于不确定怎么组合，就需要将所有的组合都列出来进行尝试。
抽象一下就是从一个集合中取出任意元素，形成唯一的组合。如[a,b,c]可组合为[a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]。
要求如下：
组合内的元素数大于0小于等于数组大小；组合内不能有重复元素，如[aab]是不符合要求的组合；组合内元素的位置随意，即[ab]和[ba]视为同一种组合；看到这里，就应该想到高中所学*的排列组合了，同样是从集合中取出元素形成一个另一个集合，如果集合内元素位置随意，就是组合，从b个元素中取a个元素的组合有种。而如果要求元素顺序不同也视为不同集合的话，就是排列，从m个元素取n个元素的排列有种。我遇到的这个需求就是典型的组合，用公式来表示就是从元素个数为n的集合中列出种组合。
文中算法用Java实现。
从排列到组合-穷举对于这种需求，首先想到的当然是穷举。由于排列的要求较少，实现更简单一些，如果我先找出所有排列，再剔除由于位置不同而重复的元素，即可实现需求。假设需要从[ABCDE]五个元素中取出所有组合，那么我们先找出所有元素的全排列，然后再将类似[AB]和[BA]两种集合去重即可。
我们又知道，那么我们先考虑一种情况，假设是，从5个元素中选出三个进行全排列。
被选取的三个元素，每一个都可以是ABCDE之一，然后再排除掉形成的集合中有重复元素的，就是5选3的全排列了。
代码是这样：
\nprivate\n\nstatic\n\nSet\n<\nSet\n<\nString\n>>exhaustion(){\n\nList\n<\nString\n>m=\nArrays\n.asList(\n"a"\n,\n"b"\n,\n"c"\n,\n"d"\n,\n"e"\n);\n\nSet\n<\nSet\n<\nString\n>>result=\nnew\n\nHashSet\n<>();\n\nint\ncount=\n3\n;\n\nfor\n(\nint\na=\n1\n;a<m.size();a++){\n\nfor\n(\nint\nb=\n0\n;b<m.size();b++){\n\nfor\n(\nint\nc=\n0\n;c<m.size();c++){\n\nSet\n<\nString\n>tempCollection=\nnew\n\nHashSet\n<>();\ntempCollection.add(m.\nget\n(a));\ntempCollection.add(m.\nget\n(b));\ntempCollection.add(m.\nget\n(c));\n\nif\n(tempCollection.size()==count){\nresult.add(tempCollection);\n}\n}\n}\n}\n\nreturn\nresult;\n}\n
对于结果组合的排重，我借用了Java中HashSet的两个特性：
元素唯一性，选取三个元素放到Set内，重复的会被过滤掉，那么就可以通过集合的大小来判断是否有重复元素了，
元素无序性，Set[AB]和Set[BA]都会被表示成Set[AB]。另外又由于元素唯一性，被同时表示为Set[AB]的多个集合只会保留一个，这样就可以帮助将全排列转为组合。可以注意得到，上面程序中count参数是写死的，如果需要取出4个元素的话就需要四层循环嵌套了，如果取的元素个取是可变的话，普通的编码方式就不适合了。
注:可变层数的循环可以用递归来实现。
从排列到组合-分治
穷举毕竟太过暴力，我们来通过分治思想来重新考虑一下这个问题：
分治思想
分治的思想总的来说就是”大事化小，小事化了”，它将复杂的问题往简单划分，直到划分为可直接解决的问题，再从这个直接可以解决的问题向上聚合，最后解决问题。
从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个元素的示例：
从5个元素中取3个元素是一个复杂问题，为了简化它，我们认为已经取出了一个元素，还要再从剩余的4个元素中取出2个，求解公式为：。从4个元素中取出2个依旧不易解决，那我们再假设又取出了一个元素，接下来的问题是如何从3个元素中取一个，公式为。从3个元素中取1个已经是个简单问题了，有三种可能，再向上追溯，与四取一、五取一的可能性做乘，从而解决这个问题。代码实现
用代码实现如下：
public\n\nclass\n\nCombination\n{\n\npublic\n\nstatic\n\nvoid\nmain(\nString\n[]args){\n\nList\n<\nString\n>m=\nArrays\n.asList(\n"a"\n,\n"b"\n,\n"c"\n,\n"d"\n,\n"e"\n);\n\nint\nn=\n5\n;\n\nSet\n<\nSet\n<\nString\n>>combinationAll=\nnew\n\nHashSet\n<>();\n\nfor\n(\nint\nc=\n1\n;c<=n;c++){\ncombinationAll.addAll(combination(m,\nnew\n\nArrayList\n<>(),c));\n}\n\nSystem\n.\nout\n.println(combinationAll);\n}\n\nprivate\n\nstatic\n\nSet\n<\nSet\n<\nString\n>>combination(\nList\n<\nString\n>remainEle,\nList\n<\nString\n>tempCollection,\nint\nfetchCount){\n\nif\n(fetchCount==\n1\n){\n\nSet\n<\nSet\n<\nString\n>>eligibleCollections=\nnew\n\nHashSet\n<>();\n\nfor\n(\nString\nele:remainEle){\n\nSet\n<\nString\n>collection=\nnew\n\nHashSet\n<>(tempCollection);\ncollection.add(ele);\neligibleCollections.add(collection);\n}\n\nreturn\neligibleCollections;\n}\nfetchCount--;\n\nSet\n<\nSet\n<\nString\n>>result=\nnew\n\nHashSet\n<>();\n\nfor\n(\nint\ni=\n0\n;i<remainEle.size();i++){\n\nList\n<\nString\n>collection=\nnew\n\nArrayList\n<>(tempCollection);\n\nList\n<\nString\n>tempRemain=\nnew\n\nArrayList\n<>(remainEle);\ncollection.add(tempRemain.remove(i));\nresult.addAll(combination(tempRemain,collection,fetchCount));\n}\n\nreturn\nresult;\n}\n}\n
其实就是递归。
直击本质-位运算
从元素的全排列找全组合，比穷举略好，但还不是最好的方法，毕竟它”绕了一次道”。
很多算法都能通过位运算巧秒地解决，其优势主要有两点：一者位运算在计算机中执行效率超高，再者由于位运算语义简单，算法大多直指本质。
组合算法也能通过位运算实现。
思想
再次考虑全组合的需求，从M个元素中取任意个元素形成组合，组合内元素不能重复、元素位置无关。
之前的方法都是从结果组合是否满足要求来考虑问题，考虑组合是否有重复元素、是否已有同样的组合等条件。如果换种思路，从待选元素上来考虑呢？
对于每个元素来说，它的状态就简单得多了，要么被放进组合，要么不放进组合。每个元素都有这么两种状态。如果从5个元素中任意取N个元素形成组合的话，用二进制位来表示每个元素是否被放到组合里，就是：
ABCDE\n0\n\n0\n\n0\n\n0\n\n1\n[E]=\n1\nABCDE\n0\n\n0\n\n0\n\n1\n\n0\n[D]=\n2\nABCDE\n0\n\n0\n\n0\n\n1\n\n1\n[DE]=\n3\n...\n
看到这里，应该就非常清楚了吧，每种组合都可以拆解为N个二进制位的表达形式，而每个二进制组合同时代表着一个十进制数字，所以每个十进制数字都就能代表着一种组合。
十进制数字的数目我们很简单就能算出来，从00000...到11111...一共有种，排除掉全都不被放进组合这种可能，结果有种。
代码实现
下面是Java代码的实现：
public\n\nclass\n\nCombination\n{\n\npublic\n\nstatic\n\nvoid\nmain(\nString\n[]args){\n\nString\n[]m={\n"A"\n,\n"B"\n,\n"C"\n,\n"D"\n,\n"E"\n};\n\nSet\n<\nSet\n<\nString\n>>combinationAll=combination(m);\n\nSystem\n.\nout\n.println(combinationAll);\n}\n\nprivate\n\nstatic\n\nSet\n<\nSet\n<\nString\n>>combination(\nString\n[]m){\n\nSet\n<\nSet\n<\nString\n>>result=\nnew\n\nHashSet\n<>();\n\nfor\n(\nint\ni=\n1\n;i<\nMath\n.pow(\n2\n,m.length)-\n1\n;i++){\n\nSet\n<\nString\n>eligibleCollections=\nnew\n\nHashSet\n<>();\n\nfor\n(\nint\nj=\n0\n;j<m.length;j++){\n\nif\n((i&(\nint\n)\nMath\n.pow(\n2\n,j))==\nMath\n.pow(\n2\n,j)){\neligibleCollections.add(m[j]);\n}\n}\nresult.add(eligibleCollections);\n}\n\nreturn\nresult;\n}\n}\n小结
排列和组合算法在实际应用中很常见，而且他们的实现方法也非常具有参考意义。总的来说：排列用递归、组合用位运算。
关于本次排列组合怎么算和排列组合算法真厉害的问题分享到这里就结束了，如果解决了您的问题，我们非常高兴。
