子集计数算法

Question

我希望能高效地解决以下问题。我有一组k元组的布尔值，预先知道每个k元组中每个值的某个比例为true。例如，我可能有以下4元组，其中每个元组至少有60％的布尔值设置为true：

(1, 0, 1, 0)
(1, 1, 0, 1)
(0, 0, 1, 0)

我希望找到一组具有特定属性的索引集：如果我查看指定索引处元组中的每个值，则至少给定分数的这些元组都具有相应位集。例如，在上面的4-tuple集合中，我可以考虑集合{0}，因为如果您查看上述元组的第零个元素，则其中三分之二为1，而2/3〜= 66％> 60％。出于同样的原因，我也可以考虑集合{2}。但是，我不能考虑{1}，因为在索引1处，只有三分之一的元组具有1，而1/3小于60％。同样，我不能使用{0,2}作为集合，因为并非所有元组都同时具有0和2位设置，所以它不足以满足要求。

我的目标是找到所有这种属性成立的集合。有没有人有一个好的算法来解决这个问题？

谢谢。

- Sergey Kucher

---

不，这完全是一个SO问题。然而，它似乎没有经过深思熟虑。解决单个{通过，失败}值向量可能更容易，然后再扩展到这些集合；扩展部分表述不清。 - Fred Foo

对我来说，问题描述很清晰。 :) - Grzegorz Wierzowiecki

Sergey - 架构有要求吗？我感觉针对单个 CPU 解决该问题可能与 GPGPU 解决方案不同。 - Grzegorz Wierzowiecki

@Grzegorz Wierzowiecki，在templatetypedef重新格式化问题之前，问题不够清晰。关于架构。代码将在客户端运行，我不能假设任何硬件情况。谢谢！ - Sergey Kucher

你写道：“我不能假设硬件的任何事情”。从计算机科学的角度来看，如果没有对硬件的假设，无论是最基本的解决方案还是复杂的解决方案，都可以在线性时间内完成。如果有任何关于硬件的假设，比如“x86”或“x86_64”，就可以进行一些优化，改变时间复杂度的常数因子。所以，让我们知道客户的目的是否有任何线索。（顺便问一下，你的客户接受“伪代码”吗？;）。对于任何实现，您需要了解一些架构信息;）。最好的Greg。 - Grzegorz Wierzowiecki

Answer 1

根据您所写的内容，可以假定架构是x86_64，并且您正在寻找实现性能，因为渐近复杂度（由于问题定义的性质，不会低于线性），我建议采用以下算法（类似C++的伪代码）：

/* N=16 -> int16; N=8 -> int8 etc. Select N according to input sizes. (maybe N=24 ;) ) */
count_occurences_intN(vector<intN> t, vector<long> &result_counters){
   intN counters[2^N]={};
   //first, count bit combinations
   for_each(v in t)
       ++counters[v];
   //second, count bit occurrences, using aggregated data 
   for(column=0; column<N; ++column){
      mask = 1 << column;
      long *result_counter_ptr = &(result_counters[column]);
      for(v=0; v<2^16; ++v)
         if( v & mask )
            ++(*result_counter_ptr);
   }
}

然后，将您的输入k比特向量拆分为N比特向量，并应用上述函数。

根据输入大小，您可以选择N=8、N=16、N=24或应用朴素方法来改善性能。

正如您所写的那样，您不能假设客户端任何内容，只需实现N={8,16,24}和朴素方法，并根据输入大小从四种实现中选择其中之一。

- Grzegorz Wierzowiecki

Answer 2

创建一个整数k向量，描述每个索引的通过次数。循环遍历您的集合，对于每个元素增加通过次数的k向量。

然后计算您的集合的基数（可以在单独的循环中或上述循环中完成）。然后循环遍历您的计数向量，并根据您的标准发出通过/失败向量。

- btilly