我希望能高效地解决以下问题。我有一组k元组的布尔值,预先知道每个k元组中每个值的某个比例为true。例如,我可能有以下4元组,其中每个元组至少有60%的布尔值设置为true:
我希望找到一组具有特定属性的索引集:如果我查看指定索引处元组中的每个值,则至少给定分数的这些元组都具有相应位集。例如,在上面的4-tuple集合中,我可以考虑集合{0},因为如果您查看上述元组的第零个元素,则其中三分之二为1,而2/3〜= 66%> 60%。出于同样的原因,我也可以考虑集合{2}。但是,我不能考虑{1},因为在索引1处,只有三分之一的元组具有1,而1/3小于60%。同样,我不能使用{0,2}作为集合,因为并非所有元组都同时具有0和2位设置,所以它不足以满足要求。
(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位设置,所以它不足以满足要求。
我的目标是找到所有这种属性成立的集合。有没有人有一个好的算法来解决这个问题?
谢谢。