2

我正在阅读http://comicjk.com/comic.php/906，其中提出了检查一个列表是否是另一个列表的排列的问题，并提出了两种解决方案。

'c Brain' 解决方案“你知道列表将始终包含四个更少的数字，并且每个数字将小于 256，因此我们可以将所有排列字节打包成 32 位整数，然后......”

“python 大脑”解决方案是对两者进行排序然后比较它们，这似乎更明显，但我对更有效（和低级）的解决方案感兴趣。

我最初的方法是：

int permutations(int a[4], int b[4]){
  int A = a[0] | a[1]*1<<8 | a[2]*1<<16 | a[3]*1<<24;
  int B = b[0] | b[1]*1<<8 | b[2]*1<<16 | b[3]*1<<24;

  unsigned int c=0, i=0;

  for( i=0xFF; i>0; i<<=8 ){
      if( 
        A&i == B&0xFF ||
        A&i == B&0xFF00 ||
        A&i == B&0xFF0000 ||
        A&i == B&0xFF000000
      ) c |= i;
  }

  if( c == 0xFFFFFFFF )
    return 1;
  return 0;
}

但是除非我能找到一种简单的方法将 A&i 和 B*0xxxxxxxxx 都定位在同一个字节上（删除我们正在查看的字节后的任何尾随 0），否则这将无法工作。所以像

(a&i>>al)>>ar == b(&j>>bl)>>br

其中 al+ar == bl+br == 4 用于确定我们正在检查的字节。

另一种方法

评论框中有人说“在 C 中，为什么不简单地动态分配一段适当大小的内存并将其视为单个数字？确实它比使用 int 慢一点，但它也不受限制包含四个或更少的元素或最大数量为 256，并且仍然比排序更快（无论是在 C 还是 Python 中）......”

如果我们可以有一个长度大于我们的最大数的数组，那么我们可以设置适当的位并比较数组，但这会提供更多的比较，因为我们会进行比较，除非我们可以有效地将其视为一个大数在c。

在 x86（我刚刚开始学习）中，我们有 SBC 指令，因此我们可以减去每个部分，如果结果全为零（我们可以用 JNE/JNZ 测试）它们是相等的。

据我所知，我们仍然需要做 / SBC 和跳跃

实际问题

我想知道如何

  1. 字节包装
  2. 将整个列表视为一个大数

可用于检查一个列表是否是另一个列表的排列（假设列表不超过 4 个项目并且每个项目小于 256）

4

3 回答 3

2

假设结果可能为“否”的优化：计算每个列表的总和（或异或，或其他一些廉价的、关联的、可交换的运算符）。如果总和不同，则答案是否定的，无需进一步测试。如果总和相同，则执行更昂贵的测试以获得明确的答案。

于 2012-06-01T23:04:57.643 回答
1

我认为您只想要一个不受排列影响的哈希值。加法作为一种方法提供。我正在考虑一种与布隆过滤器兼容的方法，这样你就可以用它做更多的事情。

布隆过滤器可以处理任意长度和任意大小的列表。它可用于查看列表是否与一组列表具有相同的排列。它可用于查看元素是否可能存在于列表中。

布隆过滤器基本上是一个位数组。您只需“或”组成列表的元素位一起生成布隆过滤器。以任何顺序具有相同元素的任何列表都将设置相同的位。对于小型列表，您可以对位数组使用整数大小的数字：

unsigned char b = a1|a2|a3|a4; // where a1..n are items (8 bit numbers)

如果您有项目 a1 和一个带有bloom b 的列表，并且想知道 a1 是否在列表中：

fPossibleMatch = ((a1&b) == a1);

如果您有两个带有 b1、b2 的任意长度的列表，并且想知道 b1 的所有项目是否可能存在于 b2 中：

fPossibleMatch = ((b1&b2) == b1);

如果您想知道具有相同 # 元素的列表 b1 和 b2 是否是彼此的排列。

fPossibleMatch = (b1==b2);

要减少误报，请扩大布隆过滤器。如果我们使用 64 位bloom，我们可以使用这个任意选择的算法来展开位：

unsigned long long b = (a1<<(a1&0x1F)) | (a2<<(a2&0x1F)) | (a3<<(a3&0x1F)) | a4<<(a4&0x1F);

我有一种感觉，我扩大绽放的算法并不好。它可能只是将所有位设置为糊状。其他人可能知道更好的方法。我想你明白了。

我认为这更好：

#define MUNGE(a) ((a)<<(((a)&7)<<3))
unsigned long long b = MUNGE(a1)|MUNGE(a2)|MUNGE(a3)|MUNGE(a4)

我不擅长创建哈希。

您仍然需要仔细检查任何具有匹配布隆过滤器的列表。误报的数量随着列表长度和元素大小的增加而增加。假阳性随着绽放大小的增加而减少。

于 2012-06-02T00:44:29.147 回答
1

使用哈希表并遍历每个列表。这将给出一个需要 O(n) 时间和 O(n) 内存的解决方案。

于 2012-06-02T18:21:28.120 回答