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

直击本质-位运算

从元素的全排列找全组合,比穷举略好,但还不是最好的方法,毕竟它”绕了一次道”。

很多算法都能通过位运算巧秒地解决,其优势主要有两点:一者位运算在计算机中执行效率超高,再者由于位运算语义简单,算法大多直指本质。

组合算法也能通过位运算实现。

思想

再次考虑全组合的需求,从 M 个元素中取任意个元素形成组合,组合内元素不能重复、元素位置无关。

之前的方法都是从结果组合是否满足要求来考虑问题,考虑组合是否有重复元素、是否已有同样的组合等条件。如果换种思路,从待选元素上来考虑呢?

对于每个元素来说,它的状态就简单得多了,要么被放进组合,要么不放进组合。每个元素都有这么两种状态。如果从 5 个元素中任意取 N 个元素形成组合的话,用二进制位来表示每个元素是否被放到组合里,就是:

A  B  C  D  E0  0  0  0  1   [E] = 1A  B  C  D  E0  0  0  1  0   [D] = 2A  B  C  D  E0  0  0  1  1   [DE] = 3...

看到这里,应该就非常清楚了吧,每种组合都可以拆解为 N 个二进制位的表达形式,而每个二进制组合同时代表着一个十进制数字,所以每个十进制数字都就能代表着一种组合。

十进制数字的数目我们很简单就能算出来,从00000... 到 11111... 一共有 种,排除掉全都不被放进组合这种可能,结果有种。


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