我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些”奇妙”的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试。
抽象一下就是从一个集合中取出任意元素,形成唯一的组合。如[a,b,c]可组合为[a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]。
要求如下:
看到这里,就应该想到高中所学习的排列组合了,同样是从集合中取出元素形成一个另一个集合,如果集合内元素位置随意,就是组合,从 b 个元素中取 a 个元素的组合有种。而如果要求元素顺序不同也视为不同集合的话,就是排列,从 m 个元素取 n 个元素的排列有种。
我遇到的这个需求就是典型的组合,用公式来表示就是从元素个数为 n 的集合中列出种组合。
对于这种需求,首先想到的当然是穷举。由于排列的要求较少,实现更简单一些,如果我先找出所有排列,再剔除由于位置不同而重复的元素,即可实现需求。假设需要从 [A B C D E] 五个元素中取出所有组合,那么我们先找出所有元素的全排列,然后再将类似 [A B] 和 [B A] 两种集合去重即可。
我们又知道,那么我们先考虑一种情况,假设是,从 5 个元素中选出三个进行全排列。
被选取的三个元素,每一个都可以是 ABCDE 之一,然后再排除掉形成的集合中有重复元素的,就是 5 选 3 的全排列了。
代码是这样:
private static Set<Set<String>> exhaustion() { List<String> m = Arrays.asList("a", "b", "c", "d", "e"); Set<Set<String>> result = new HashSet<>(); int count = 3; for (int a = 1; a < m.size(); a++) { for (int b = 0; b < m.size(); b++) { for (int c = 0; c < m.size(); c++) { Set<String> tempCollection = new HashSet<>(); tempCollection.add(m.get(a)); tempCollection.add(m.get(b)); tempCollection.add(m.get(c)); // 如果三个元素中有重复的会被 Set 排重,导致 Set 的大小不为 3 if (tempCollection.size() == count) { result.add(tempCollection); } } } } return result; }
对于结果组合的排重,我借用了 Java 中 HashSet 的两个特性:
可以注意得到,上面程序中 count 参数是写死的,如果需要取出 4 个元素的话就需要四层循环嵌套了,如果取的元素个取是可变的话,普通的编码方式就不适合了。
注: 可变层数的循环可以用递归来实现。
穷举毕竟太过暴力,我们来通过分治思想来重新考虑一下这个问题:
分治的思想总的来说就是”大事化小,小事化了”,它将复杂的问题往简单划分,直到划分为可直接解决的问题,再从这个直接可以解决的问题向上聚合,最后解决问题。
从 M 个元素中取出 N 个元素整个问题很复杂,用分治思想就可以理解为:
还是从 5 个元素中取 3 个元素的示例:
用代码实现如下:
public class Combination { public static void main(String[] args) { List<String> m = Arrays.asList("a", "b", "c", "d", "e"); int n = 5; Set<Set<String>> combinationAll = new HashSet<>(); // 先将问题分解成 五取一、五取二... 等的全排列 for (int c = 1; c <= n; c++) { combinationAll.addAll(combination(m, new ArrayList<>(), c)); } System.out.println(combinationAll); } private static Set<Set<String>> combination(List<String> remainEle, List<String> tempCollection, int fetchCount) { if (fetchCount == 1) { Set<Set<String>> eligibleCollections = new HashSet<>(); // 在只差一个元素的情况下,遍历剩余元素为每个临时集合生成多个满足条件的集合 for (String ele : remainEle) { Set<String> collection = new HashSet<>(tempCollection); collection.add(ele); eligibleCollections.add(collection); } return eligibleCollections; } fetchCount--; Set<Set<String>> result = new HashSet<>(); // 差多个元素时,从剩余元素中取出一个,产生多个临时集合,还需要取 count-- 个元素。 for (int i = 0; i < remainEle.size(); i++) { List<String> collection = new ArrayList<>(tempCollection); List<String> tempRemain = new ArrayList<>(remainEle); collection.add(tempRemain.remove(i)); result.addAll(combination(tempRemain, collection, fetchCount)); } return result; } }
其实现就是递归,关于递归和分治,有兴趣可以看一下隐藏篇:递归和分治。
从元素的全排列找全组合,比穷举略好,但还不是最好的方法,毕竟它”绕了一次道”。
很多算法都能通过位运算巧秒地解决,其优势主要有两点:一者位运算在计算机中执行效率超高,再者由于位运算语义简单,算法大多直指本质。
组合算法也能通过位运算实现。
再次考虑全组合的需求,从 M 个元素中取任意个元素形成组合,组合内元素不能重复、元素位置无关。
之前的方法都是从结果组合是否满足要求来考虑问题,考虑组合是否有重复元素、是否已有同样的组合等条件。如果换种思路,从待选元素上来考虑呢?
对于每个元素来说,它的状态就简单得多了,要么被放进组合,要么不放进组合。每个元素都有这么两种状态。如果从 5 个元素中任意取 N 个元素形成组合的话,用二进制位来表示每个元素是否被放到组合里,就是:
A B C D E
0 0 0 0 1 [E] = 1
A B C D E
0 0 0 1 0 [D] = 2
A B C D E
0 0 0 1 1 [DE] = 3
...
看到这里,应该就非常清楚了吧,每种组合都可以拆解为 N 个二进制位的表达形式,而每个二进制组合同时代表着一个十进制数字,所以每个十进制数字都就能代表着一种组合。
十进制数字的数目我们很简单就能算出来,从00000...到11111...一共有种,排除掉全都不被放进组合这种可能,结果有种。
下面是 Java 代码的实现:
public class Combination { public static void main(String[] args) { String[] m = {"A", "B", "C", "D", "E"}; Set<Set<String>> combinationAll = combination(m); System.out.println(combinationAll); } private static Set<Set<String>> combination(String[] m) { Set<Set<String>> result = new HashSet<>(); for (int i = 1; i < Math.pow(2, m.length) - 1; i++) { Set<String> eligibleCollections = new HashSet<>(); // 依次将数字 i 与 2^n 按位与,判断第 n 位是否为 1 for (int j = 0; j < m.length; j++) { if ((i & (int) Math.pow(2, j)) == Math.pow(2, j)) { eligibleCollections.add(m[j]); } } result.add(eligibleCollections); } return result; } }
排列和组合算法在实际应用中很常见,而且他们的实现方法也非常具有参考意义。总的来说:排列用递归、组合用位运算。