查找大数组中最常见的六个字母组合

Question

我有一个矩阵6000x20，包含的数字范围是1-80。我需要查找出现在矩阵中的所有六元组。我需要最高效和最快的解决方案。 我目前的解决办法是这样做的： 1.我从矩阵中取第一行并产生所有的六行字（38600在一行中） 2.我把每一个六行字与其他5999行进行比较并计算它们 3.我把它们写入一个文件，因为我的存储空间已满相当快 4.我把第二排和生成所有sextuplets我又

这种算法是非常糟糕和IM意识到这一点，因为我有38600X6000比较和可能的文件写入完成所有步骤，我有很多重复的六重音。但我不知道，因为我不能使用这种大小的变量。

我需要的算法解决方案，因此我可以在Matlab/JAVA/C++ /蟒

Answer 1

由于值的范围为1-80，可能sextuplets的总数是“唯一”的一个稍微超过3亿写（准确地说300,500,200）。由于矩阵中只有6000行，因此任何六进制数的最大计数都是6000，所以计数可以很容易地适合两个字节的整数（假设存在于C++实现中，则为uint16_t）。三亿两个字节的整数总共600兆字节，你可能已经有了。所以一个简单的算法就是创建计数向量，初始化为零，然后迭代矩阵中的所有行;对于每一行，遍历38,760个六元组，并对每个六元组递增相应的计数。

诀窍是计算出计数向量中的哪个元素对应给定的六个数字集合。碰巧，只要六个字符的数字从最小到最大，这并不难。 （这不是一个限制，因为你需要有一些规范的顺序为六元组，并按顺序排序是一个简单的规范顺序。）

要了解如何生成索引，请考虑如何（假设）枚举所有300,500,200来自集合{1..80}的六个整数的组合。首先，我们列举以1开始的组合，并继续使用集合{2..80}中的五个整数。然后，我们枚举以2开始的组合，并继续使用集合{3..80}中的五个整数。然后，我们枚举以3开始的组合，并继续使用集合{4..80}中的5个整数。等等。在每个起点的枚举中，我们递归地应用相同的算法。

现在，让我们把它列在头上。假设我们有一些六联{a,b,c,d,e,f}。请问之后有多少个六进制码出现那sextuplet？

• 首先，所有以大于a的值开始的六个字符串。由于六个字符串是有序的，如果一个六元组的起始值大于a，那么它的所有值都大于a，这意味着它是来自集合{a+1..80}的六个值的某种组合，其中有 _80-a C 。

• 然后，所有六个字符串都以a开头，并继续五元组，第一个值大于b。通过上述相同的逻辑，这样的六个小组的数目是 _80-b C 。

• 然后，存在与开始a,b并继续四方其第一值大于c更大所有sextuplets：共 _80-C的C

• 等等

所以以下{a,b,c,d,e,f} sextuplets总数恰恰是：

_80-AÇ + _80-BÇ + _80-CÇ + _80-dÇ + _80-EÇ + _80-Fç

有趣关于上面的等式是，有六个变量之间没有相互作用。我们可以通过创建六个查找表来计算值，其值为1到80之间的值，以及i的值从1到6.然后我们可以计算（逆）指数通过只进行六次查找并将值加在一起来确定任何六进制数。 （如果需要的话，我们可以从组合总数中减去反向索引以得到正向索引，但是在这种情况下，我们需要的是从组合到整数的双向反射，反向索引将正常工作。）

在算法结束时，有必要将计数索引变回六个字节。这可以使用相同的查找表，通过执行二进制搜索的连续操作来完成：首先，在i == 6的查找表中通过二进制搜索找到值a，然后减去相应的索引并继续搜索余数i == 5的查找表等等（实际上，由于查找表很小，可能会发现线性搜索比二元搜索更快，但它可能没有多大区别。）