algorithm - 查找三个排列列表的可能组合数

Question

我正在为这个任务寻找解决方案:

共有三个置换整数列表:

 index
 0 1 2 3
[2,4,3,1]
[3,4,1,2]
[1,2,4,3]

我想知道列表中三元组的组合有多少。例如，第二个列表向右旋转一位，第三个列表向左旋转一位:

 0 1 2 3
[2,4,3,1]
 3 0 1 2
[2,3,4,1]
 1 2 3 0
[2,4,3,1]

将产生两种组合 (2,2,2) 和 (1,1,1)。我只对组合的数量感兴趣，而不是实际组合本身。

列表的长度始终为 N。据我了解，至少有一种组合，最大为 N。

我已经编写了一个命令式解决方案，使用了三个嵌套的 for 循环，但是对于更大的问题规模(例如 N > 1000)，这很快就会变得难以忍受。

是否有比蛮力(尝试所有组合)更有效的方法？也许是一些聪明的算法或数学技巧？

编辑:
我正在改写问题以使其(希望)更清楚:
我有一个列表 [1..N] 的 3 个排列。
列表可以单独向左或向右旋转，直到某些索引的元素排成一行。在上面的例子中是:
将列表 2 右旋 1
左旋转列表 3 1
现在列对齐 2 和 1。
我还在上面的示例中添加了索引。如果仍然不清楚，请告诉我。

到目前为止我的代码:

#include <iostream>

int
solve(int n, int * a, int * b, int * c)
{
  int max = 0;
  for (int i = 0; i < n; ++i) {
    int m = 0;
    for (int j = 0; j < n; ++j) {
      if (a[i] == b[j]) {
        for (int k = 0; k < n; ++k) {
          if (a[i] == c[k]) {
            for (int l = 0; l < n; ++l) {
              if (a[l] == b[(l+j) % n] && a[l] == b[(l+k) % n]) {
                ++m;
              }
            }
          }
        }
      }
    }
    if (m > max) {
      max = m;
    }
  }
  return max;
}

int
main(int argc, char ** argv)
{
  int n = 5;

  int a[] = { 1, 5, 4, 3, 2 };
  int b[] = { 1, 3, 2, 4, 5 };
  int c[] = { 2, 1, 5, 4, 3 };

  std::cout << solve(n, a, b, c) << std::endl;

  return 0;
}

Answer 1

这是一个有效的解决方案:

1. 假设我们从第一个列表中选择了一个固定元素，我们希望将它与第二个和第三个列表中具有相同值的元素进行匹配。它唯一地确定了第二个和第三个列表的旋转(我们可以假设第一个列表永远不会旋转)。它给了我们一对两个整数:(这个元素在第一个列表中的位置减去它在第二个列表中的位置模 N，第一个和第三个列表相同)。

2. 现在我们可以遍历第一个列表的所有元素并生成这些对。

3. 答案是出现次数最多的一对。

如果我们使用标准排序来查找最频繁的对，则时间复杂度为 O(N * log N)；如果我们使用基数排序或哈希表，则时间复杂度为 O(N)。