给定两个集合，每个集合都包含整数值，如何找到包含所有可能的成对值的集合ORs这两组的值？例如。 （所有数字都是二进制）
{1, 10} x {100, 1000} = {101, 1001, 110, 1010}
{1, 10} x {11, 101} = {11, 101, 111}
第一个示例产生完整的四种组合，而第二个示例仅产生三种组合，因为两个集合共享一些位。显然结果可以计算为O(m*n)，但是考虑到在许多情况下结果的大小将小于m*n?
在某些情况下，结果集明显小于m*n (e.g. {1, 11, 111} x {10, 110} = {11, 111}） - 但我无法以足够通用的方式来确定所有这些情况的确切性质来获得算法。理想情况下它应该运行在O(r), where r是结果集的大小。可能有某种方法可以对源集进行分区，使用动态编程方法构建结果，或者以这种方式做其他事情，但目前我找不到它。
虽然我对此了解不多，但我想知道是否根据数据的基数，使用trie http://en.wikipedia.org/wiki/Trie一套可以提高效率。当遍历另一个设置为or对于索引集合，如果可以确定比特与索引集合中的当前整数匹配，则可以跳过树的整个分支。
另一种优化可能是，如果我们已经有 2^(n-1) 个长度为 n 的结果，则跳过该长度的所有配对；例如，有八个可能的整数，长度为四位。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
