Найти число возможных комбинаций три перестановки списков

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> 1000) это быстро становится невыносимым.

Есть ли более эффективный подход, чем грубая сила (попытка всех комбинаций) ?. Может быть, какой-то умный алгоритм или математический трюк?

Edit:
Я перефразировать вопрос, чтобы сделать это (надеюсь) более ясно:
У меня есть 3 перестановки списка [1..n].
Списки могут быть индивидуально повернуты влево или вправо, пока элементы для некоторых индексов не совпадут. В приведенных выше примере это будет:
список правого поворота 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 * N журнал), если мы используем стандартный вид, чтобы найти наиболее часто пары или O (N), если мы используем базисное сортировки или хэш-таблицу.

Answer 2

Вы можете сделать это путем создания все комбинации, как:
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 числами, которые могут быть друг с другом число списки, которые вы получили.

, если это не так ясно, пожалуйста, скажите мне