Number of ways to form array using only 3 elements?

Question

We need to find out the number of ways we can form a N-length array(A) consisting only 3 elements (1,2 and 3).

There are few constraints on how array's adjacent elements can be placed in the array:

Number of adjacent elements pairs (A[i], A[i + 1]) of a certain type cannot exceed as given in the problem statement.

example :

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

For adjacent elements of type A[i] == A[i + 1], they can be any number of times in the array

1, 1 : inf
2, 2 : inf
3, 3 : inf

Sample Case :

Input :

N = 3

1, 2 : 1 
1, 3 : 1
2, 1 : 1
2, 3 : 0 
3, 1 : 0
3, 2 : 0   

Output :

12

Explanation :

[1, 2, 1] , here { (1,2) : 1, (2,1) : 1 }, so valid 
[1, 2, 2]
[1, 1, 2]
[2, 1, 2]

[1, 3, 3] , here { (1,3) : 1, (3,3) : 1 }, so valid 
[1, 1, 3]
[2, 1, 3] , here { (2,1) : 1, (1,3) : 1 }, so valid 

[2, 1, 1] , here { (2,1) : 1, (1,1) : 1 }, so valid 
[2, 2, 1]     

[1, 1, 1] , here { (1,1) : 2 }, so valid, as adj-pairs (x, x) can be any number of times.
[2, 2, 2]
[3, 3, 3]

All other combinations of 1,2,3 are invalid like :
[3, 1, 1], [2, 3, 1], etc.

Constraints

1 <= N <= 10^6

0 <= limit[i][j] <= 10^5

where N = array length and limit[i][j] = number of pairs of type (i, j)

Pseudocode :

main() :
   ways = 0;
   for(p = 1; p <= 3; p++) :
       ways += num_ways(p, 1, n, A, limit);
   return ways;


num_ways(prev, i, n, A[], limit[][]) :
  
  if(i == n) return 1;
  
  ways = 0;
  for(e = 1; e <= 3; e++):
      if(limit[prev][e] > 0) 
          limit[prev][e] -= 1;
          ways += num_ways(e, i + 1, A, limit);
          limit[prev][e] += 1;

  return ways;

, where limit[i][j] means max number of adjacent-pairs of value (i, j) that can be present in array

Pseudocode Explanation :

I tried to solve this using recursion (brute-force), i.e at every function call insert any element (1,2,3) at index i and check if (A[i - 1], A[i]) pair hasn't exceed the limit as per given in problem statement, and if yes then return else continue calling func() while i != n.

This approach is fine, but it's giving TLE(time limit exceeded) error, hence it's not the most optimal way to find out number of ways to form array.

Is there any other efficient way to solve this problem ?

Answer 1

The approach I would take is NOT to create the actual array. I would instead approach it by analyzing your restrictions.

1, 2 : 2
1, 3 : 3
2, 1 : 1
2, 3 : 0
3, 1 : 4
3, 2 : 3

So there are only a limited number of transitions allowed in your system.

So my starting point would be to count all of the possible transition combinations, associated with a min-length n for each. This can be performed using some brute force method, although there may or may not be a more efficient method.

A sample of the output resulting from the brute force method should be as below...

• min-length 2 transitions:

1, 2
1, 3
2, 1
3, 1
3, 2
So, n-2 pattern count = 5.

• min-length 3 transitions:

1, 2, 1
1, 3, 1
1, 3, 2
2, 1, 2
2, 1, 3
3, 1, 2
3, 1, 3
3, 2, 1
So, n-3 pattern count = 8.

Once we have calculated all of the possible combination counts for each minimum length, we perform permutations mathematics based on the actual input n. We can reuse the original structure we have created to perform calculations for multiple input of n very fast.

For example, where n = 3, we start with 3 for null-transitions. Then we add 8 for no permutations of transitions requiring min-length n. Then we calculate the permutations for min-length n - 1, n - 2, etc until n - x = 2. Permutations are calculated by shifting the position of each transition with excess space. i.e. where n = 3 and min-n = 2, excess space = 1, so we can shift the transition left/right by 1, giving us 2 patterns instead of 1. So since there are 5 patterns that are of length 2, and each can be transitioned to 2 patterns, that would give us 10 patterns. So we have 10 + 8 + 3 = 21.

To clarify the maths further, I'll use n = 10 on the n-3 pattern. We have 9 transition slots and 2 transitions and can apply permutation mathematics:

1. The first transition may occur anywhere in the first 8 of 9 transition slots. Which slot is selected determines where the second transition may go, but lets ignore that for now. Then this becomes 9!/7!. However, this includes all out of order combinations, so we want to further divide that by 2!. So we have 9 * 4 = 36 combinations, * pattern count of n-3 patterns = 36 * 8. Add this to the n-2 patterns, n-4 patterns, etc...

This becomes generalized to:

• sum(i: n ... 1) { patternCount(i) * ((n - 1)!)/(n - i - 1)!/i! }