我的个人博客 个人技术日志

迷人的算法-排列组合

最近工作中碰到一个需求:我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些”奇妙”的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试。

抽象一下就是从一个集合中取出任意元素,形成唯一的组合。如 [a,b,c] 可组合为 [a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]

要求如下:

  • 组合内的元素数大于 0 小于等于 数组大小;

  • 组合内不能有重复元素,如 [aab] 是不符合要求的组合;

  • 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合;

看到这里,就应该想到高中所学习的排列组合了,同样是从集合中取出元素形成一个另一个集合,如果集合内元素位置随意,就是组合,从 b 个元素中取 a 个元素的组合有 种。而如果要求元素顺序不同也视为不同集合的话,就是排列,从 m 个元素取 n 个元素的排列有 种。

我遇到的这个需求就是典型的组合,用公式来表示就是从元素个数为 n 的集合中列出 种组合。

文中算法用 Java 实现。

从排列到组合-穷举


对于这种需求,首先想到的当然是穷举。由于排列的要求较少,实现更简单一些,如果我先找出所有排列,再剔除由于位置不同而重复的元素,即可实现需求。假设需要从 [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 的两个特性:

  • 元素唯一性,选取三个元素放到 Set 内,重复的会被过滤掉,那么就可以通过集合的大小来判断是否有重复元素了,

  • 元素无序性,Set[A B] 和 Set[B A] 都会被表示成 Set[A B]。

  • 另外又由于元素唯一性,被同时表示为 Set[A B] 的多个集合只会保留一个,这样就可以帮助将全排列转为组合。

可以注意得到,上面程序中 count 参数是写死的,如果需要取出 4 个元素的话就需要四层循环嵌套了,如果取的元素个取是可变的话,普通的编码方式就不适合了。

注: 可变层数的循环可以用 递归 来实现。


作者:admin 分类:未分类 浏览:38 评论:0
留言列表
发表评论
来宾的头像