c - 有效地测试一个列表是否是另一个列表的排列

Question

我正在阅读 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 和跳跃

实际问题

我想知道如何

字节打包

将整个列表视为一个大数

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

Answer 1

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