Find the number of possible combinations of three permuted lists

I'm looking for a solution for this task:

There are three permuted integer lists:

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

I'd like to know how many combinations of three tuples across the lists there are. For example, after rotating the second list by one to the right and the third list by one to the left:

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

would result in two combinations (2,2,2) and (1,1,1). I'm only interested in the number of combinations, not the actual combinations themselves.

The lists have always the same length N. From my understanding, there are is at least one combination and maximally N.

I've written an imperative solution, using three nested for loops, but for larger problems sizes (e.g. N > 1000) this quickly becomes unbearable.

Is there are more efficient approach than brute force (trying all combinations)?. Maybe some clever algorithm or a mathematical trick?

Edit: I'm rephrasing the question to make it (hopefully) more clear: I have 3 permutations of a list [1..N]. The lists can be individually rotated left or right, until the elements for some indexes line up. In the above example that would be: Right rotate list 2 by 1 Left rotate list 3 by 1 Now the columns are aligned for 2 and 1. I've also added the indexes the example above. Please tell me, if it's still unclear.

My code so far:

#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;
}

Answers


Here is an efficient solution:

  1. Let's assume that we have picked a fixed element from the first list and we want to match it to the elements from the second and the third list with the same value. It uniquely determines the rotation of the second and the third list(we can assume that the first list is never rotated). It gives us a pair of two integers: (the position of this element in the first list minus its position in the second list modulo N, the same thing for the first and the third list).

  2. Now we can iterate over all elements of the first list and generate these pairs.

  3. The answer is the number of ocurrences of the most frequent pair.

The time complexity is O(N * log N) if we use standard sort to find the most frequent pair or O(N) if we use radix sort or a hash table.


You can make it by creating all combinations like: 0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1

Each 0 / 1 can be your array

This code can help you creating this list above:

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;
}

it's also either can be with 0/1/2 numbers which each other number can be the lists you got.

if it's not so clear please tell me


Need Your Help

Hard query with aggregation

sql oracle average

I'm using Oracle SQL, and i need help with a hard query.

random number array in Verilog

arrays random verilog system-verilog

I want to test all possible combinations of inputs to a verilog module. I have been able to do generate these inputs by building an array with a nested for loop. However I want to go through the ar...