Number of ways to form array using only 3 elements?

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

1, 2 : 21, 3 : 32, 1 : 12, 3 : 03, 1 : 43, 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, 21, 32, 13, 13, 2So, n-2 pattern count = 5.

• min-length 3 transitions:

1, 2, 11, 3, 11, 3, 22, 1, 22, 1, 33, 1, 23, 1, 33, 2, 1So, 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! }

From the computational standpoint, you face two issues:Memory space (see below), and performance.

The number of candidate numbers is m=3^N (mmax=3^Nmax=3^(10^6)).

You have to build a list of constraints, ic=1...nc.Evidently, the maximum number of constraints is ncmax=3^2=9. If pairs (i,i) will always be unconstrained, ncmax=3*(3-1)=6. Each pair that is further unconstarined counts against this total.Your "standard" order (ic,pair) seems to be{(1,(1,2)), (2,(1,3)), (3,(2,1)), (4,(2,3)), (5,(3,1)), (6,(3,2))}.

Each constraint is made up of:

1. The constraint function, which takes a number i and returns the number of occurences pc(i,ic) (or pc(i,pair)) of the condition/pair to verify.
2. The maximum number of allowed occurrences pcmax(ic) (or pcmax(pair)).

In your first "Sample case", with the number i=121, pc(121,(1,2))=1, pcmax((1,2))=1 -> ok.

A VERY brute force approach (without recursion):

nways = 0for i in 1:m   # (you have to find how to loop on the very large number of numbers)    for ic in 1:nc        c = pc(i,ic)        cmax = pcmax(i)        if (c <= cmax)            nways += 1

A number of (possibly significant) optimizations of the algorithm are possible, perhaps by using recursion.

1. In the evaluation of pc(i,ic), if the method traverses each pair in number i for counting, you may also pass pcmax(ic) to exit early with "failure" without completely checking all pairs in i.
2. If your values of pcmax(ic) are always small compared to N.You mention 1<=pcmax(pair)<=P, with P=10^5.The case P<<N perhaps warrants a different approach, but you state no relation between P and N, so this is in principle not the case.
   Note that you "Sample case" uses pcmax((2,3))=pcmax((3,1))=pcmax((3,2))=0, which contradicts your last general condition 1<=pcmax(pair)<=P.
3. Else?

Without any further specification/restriction of the problem, I am not sure you can do much better.

Memory space

1 digit of your candidate numbers -> 2 bits (1,2,3). (This is 25% waste of space)
10^6 digits -> 10^6*2 bits = 10^6/4 bytes ~ 256 kB, if packing 4 digits in one byte. Or you can use one byte per digit, which takes up to ~1MB.

Your question asks how can we do that more efficient. I assume you refer to runtime, and not to memory. I am going to suggest a solution, that will probably be fast, at a cost of a really high memory consumption. Generally speaking, usually they come one on the expense of the other.

I would build that iteratively. First let's prepare the data we need. What do we need? We will construct a map, where the key is the number at the left, and the value is a map itself. The second map maps between any possible right value, to the amount it can be. Let's generate such a map from your example:

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

we will generate the map:

Map(  1 -> Map(2 -> 2, 3 -> 3),  2 -> Map(1 -> 1),  3-> Map(1 -> 4, 2 -> 3))

Given that map, now we can start building the solution.

We will initiate a sequence of tuples. We will call it allPossibleSolutions. What those tuples are going to be? The first element, will be the number last added to the result sequence. The second value is going to be the the remaining possible pairs. This means that on every iteration, we need to decrease the used pair from the map.

On every iteration, we are going to add to the result the length of the queue, because we can always complete the series with repeating the last element until we get to an N-length series.

I assume we already have the map, with the remaining pairs, which I'll refer to as remainingPairs. Now, let's write some code:

intermediateQueue = Queue((1 to N).map(i => remainingPairs))numWays = Nfor (int i = 0; i < n - 1; i++) { // The first iteration was the line above  for (int j = 0; j < intermediateQueue.length; j++) {    (lastInSeries, currentRemainingPairs) = intermediateQueue.pull()    toContinueWith = currentRemainingPairs.get(lastInSeries) // that is a map from the next element to the count it can still be used    for ((value, repeatCount) <- toContinueWith) {      if (repeatCount > 0) {        newToContinueWith = toContinueWith.copy // This is very important!! otherwise you'll override yourself between iterations.        newToContinueWith[value] = newToContinueWith[value] - 1        newRemainingPairs = remainingPairs.copy        newRemainingPairs[lastInSeries] = newToContinueWith        intermediateQueue.add((value, newRemainingPairs))      }    }    numWays += iterlength  }}

Let's try to follow up that code with the given example. We already build the initial map.

We initiate the queue with (1 -> map, 2 -> map, 3 -> map)

i=0numWays = 3 // That represents the series (1,1,1) (2,2,2) (3,3,3)   j = 0  (lastInSeries, currentRemainingPairs) = (1, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3)))  toContinueWith = Map(2 -> 2, 3 -> 3)    (value, repeatCount) = (2, 2)      newToContinueWith = Map(2 -> 1, 3 -> 3)      newRemainingPairs = Map(1 -> Map(2 -> 1, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3))      intermediateQueue.add(2, newRemainingPairs)    (value, repeatCount) = (3, 3)      newToContinueWith = Map(2 -> 2, 3 -> 2)      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 2), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3))      intermediateQueue.add(3, newRemainingPairs)  j = 1    (lastInSeries, currentRemainingPairs) = (2, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(1 -> 4, 2 -> 3)))  toContinueWith = Map(1 -> 1)    (value, repeatCount) = (1, 1)      newToContinueWith = Map(1, 0)      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 4, 2 -> 3))      intermediateQueue.add(1, newRemainingPairs)  j = 2    (lastInSeries, currentRemainingPairs) = (3, Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 1), 3-> Map(2 -> 3)))  toContinueWith = Map(1 -> 4)    (value, repeatCount) = (1, 4)      newToContinueWith = Map(1, 3)      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 3, 2 -> 2))      intermediateQueue.add(1, newRemainingPairs)  toContinueWith = Map(2 -> 3)    (value, repeatCount) = (2, 3)      newToContinueWith = Map(2, 2)      newRemainingPairs = Map(1 -> Map(2 -> 2, 3 -> 3), 2 -> Map(1 -> 0), 3-> Map(1 -> 4, 2 -> 2))      intermediateQueue.add(2, newRemainingPairs)  numWays += 5 // That represents the following: (1,2,2) (1,3,3) (2,1,1) (3,1,1) (3,2,2)i = 1

We conrinue another cycle like that, and get the following valid series:

(1,2,1) (1,3,1) (1,3,2) (2,1,2) (2,1,3) (3,1,2) (3,1,3) (3,2,1)

P.S

We can even improve that algorithm a bit by removing empty mappings. it will save a lot of compute, and memory.