用于查找一组位串的基础的算法？

2018-06-03 04:38:49

这是我用C ++编写的diff实用程序。

我有n个字符集{“a”，“abc”，“abcde”，“bcd”，“de”}（从k = 5个不同的字母的字母表中取得）的列表。我需要一种方法来观察整个列表可以通过字符集{“a”，“bc”，“d”，“e”}的分离来构造。也就是说，“b”和“c”是线性相关的，而每一对字母都是独立的。

在比特转换版本中，上面的字符集表示为{10000,11100,11111,01110,00011}，并且我需要一种观察它们都可以通过将来自较小集合{10000 ，01100，00010，00001}。

换句话说，我相信我正在寻找{0,1} k中一组n个不同位向量的“离散基”。本文声称一般问题是NP完全...但幸运的是，我只寻找小案例的解决方案（k <32）。

我可以想到用于生成基础的非常愚蠢的算法。例如：对于k2对字母中的每一对，尝试证明（通过O（n）搜索）他们依赖。但我真的觉得我有一个有效的比特旋转算法，我还没有找到。有人知道吗？

编辑：我最终并不真的需要解决这个问题，毕竟。但是我仍然想知道是否有一个简单的双向解决方案。

我正在考虑一个不相交的集合数据结构，就像联合查找开启它的头（而不是结合节点，我们将它们分开）。

算法：

创建一个数组main ，将所有位置分配给同一个组，然后：

for each bitstring curr
  for each position i
    if (curr[i] == 1)
      // max of main can be stored for constant time access
      main[i] += max of main from previous iteration

然后， main中的所有不同数字都是不同的集合（可能使用实际的union-find算法）。

例：

所以， main = 22222 。（我不会使用1作为组来减少可能的混淆，因为curr使用位串）。

curr = 10000
main = 42222 // first bit (=2) += max (=2)

curr = 11100
main = 86622 // first 3 bits (=422) += max (=4)

curr = 11111
main = 16-14-14-10-10

curr = 01110
main = 16-30-30-26-10

curr = 00011
main = 16-30-30-56-40

然后用不同的数字分割：

{10000, 01100, 00010, 00001}

改进：

为了减少main增加的速度，我们可以替换

main[i] += max of main from previous iteration

同

main[i] += 1 + (max - min) of main from previous iteration

编辑：编辑基于j_random_hacker的评论

以空间为代价，你可以结合愚蠢算法的通行证。

创建一个称为violations的位向量，其长度为(k - 1) k / 2位（对于k = 32 ，所以为496）。对字符集进行一次遍历。对于每个字母和每对字母，查找违规（即对这些字母进行XOR ， OR将结果转换为violations的相应位置）。完成后，取消并读取剩下的内容。

您可以试试主成分分析 。有一些PCA设计用于二进制或更一般的分类数据。

链接地址: http://www.djcxy.com/p/11023.html

上一篇: Algorithm for finding basis of a set of bitstrings?