直击本质-位运算
从元素的全排列找全组合,比穷举略好,但还不是最好的方法,毕竟它”绕了一次道”。
很多算法都能通过位运算巧秒地解决,其优势主要有两点:一者位运算在计算机中执行效率超高,再者由于位运算语义简单,算法大多直指本质。
组合算法也能通过位运算实现。
思想
再次考虑全组合的需求,从 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...
一共有 种,排除掉全都不被放进组合这种可能,结果有种。