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

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

您可以通过创建所有组合来实现：
0,0,0
0,0,1
0,1,0
0,1,1
1,0,0
1,0,1
1,1,0
1,1,1

每个 0 / 1 都可以是你的数组

此代码可以帮助您创建上面的列表：

private static ArrayList<String> getBinaryArray(ArrayList<Integer> array){

//calculating the possible combinations we can get
int possibleCombinations = (int) Math.pow(2, array.size());

//creating an array with all the possible combinations in binary
String binary = "";
ArrayList<String> binaryArray = new ArrayList<String>();
for (int k = 0; k <possibleCombinations; k++) {

    binary = Integer.toBinaryString(k);

    //adding '0' as much as we need
    int len = (array.size() - binary.length());
    for (int w = 1; w<=len; w++) {
        binary = "0" + binary;
    }

    binaryArray.add(binary);
}

return binaryArray;
}

它也可以是 0/1/2 数字，每个数字可以是你得到的列表。

如果不是很清楚请告诉我

Answer 2

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

假设我们从第一个列表中选择了一个固定元素，我们希望将它与第二个和第三个列表中具有相同值的元素匹配。它唯一地确定了第二个和第三个列表的旋转（我们可以假设第一个列表永远不会旋转）。它给了我们一对两个整数：（这个元素在第一个列表中的位置减去它在第二个列表中的位置模 N，第一个和第三个列表相同）。
现在我们可以遍历第一个列表的所有元素并生成这些对。
答案是出现次数最多的一对。

如果我们使用标准排序找到最频繁的对，时间复杂度为 O(N * log N)，如果我们使用基数排序或散列，则时间复杂度为 O(N) table。

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

Find the number of possible combinations of three permuted lists

algorithm

math

combinatorics