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 : 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! }

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 = 0
for 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 : 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

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 = N
for (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=0
numWays = 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.

Since you are asking for the count and not for the list of permutation, it's easy to solve, if you split it into two steps:

1. precalculate all possible combinations until nothing is left to combine. This yields a set of solutions for each length = 2,3,...
2. to obtain the count for a given len, use the solutions up to the wanted length and extend the the solutions with a smaller len. Luckily this can be done with a simple formula, which is known as distributing k balls into n buckets. x = (( n over k )) = ( k+n+1 over n-1) Multiply that value x with the count of variants and sum that up.

Here is a working example code:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class A3 {

    static class P {
        List<Integer> list;
        Map<Integer, Integer> avail;

        public P(List<Integer> list, Map<Integer, Integer> pair2n) {
            this.list = list;
            avail = pair2n;
        }
        
        public String toString() {
            return list.toString();
        }
    }
    
    // sequences with count as array of {a, b, n}
    int limited[][] = {
            {1,2,1},
            {1,3,1},
            {2,1,1},
            {2,3,0},
            {3,1,0},
            {3,2,0}
    };

    // lookup   a*10 + b -> n
    private TreeMap<Integer, Integer> pair2n;

    // precalculated combinations
    private List<ArrayList<P>> precalc = new ArrayList<>();
    
    /**
     * Simple main stub
     * @param args unused
     */
    public static void main(String[] args) {
        A3 a3 = new A3();
        a3.init();
        a3.precalc();
        a3.solve();
    }

    /**
     * Fill map from array.
     */
    private void init() {
        pair2n = new TreeMap<Integer, Integer>();
        for (int []x : limited) {
            pair2n.put(x[0] * 10 + x[1], x[2]);
        }
    }

    /**
     * Calculate all valid combinations until all counters are 0.
     */
    private void precalc() {
        // pre-calculate solutions without 1,1 2,2 and 3,3 until all counters are 0
        int prelen = 0;
        for (Integer n : pair2n.values()) {
            prelen += n;
        }
        
        System.out.println("precalc 2.." + prelen);
        ArrayList<P> current = new ArrayList<>();
        current.add(new P(Arrays.asList(1), pair2n));
        current.add(new P(Arrays.asList(2), pair2n));
        current.add(new P(Arrays.asList(3), pair2n));
        precalc.add(current);
        
        for (int i = 2;; ++i) {
            ArrayList<P> next = new ArrayList<>();
            for (P p : current) {
                for (Entry<Integer, Integer> e : p.avail.entrySet()) {
                    // count > 0 and last number matches current sequence
                    if (e.getValue() > 0 && e.getKey() / 10 == p.list.get(p.list.size() - 1)) {
                        ArrayList<Integer> al = new ArrayList<Integer>(p.list);
                        al.add(e.getKey() % 10);
                        Map<Integer, Integer> map = new TreeMap<>(p.avail);
                        map.put(e.getKey(), e.getValue() - 1);
                        P np = new P(al, map);
                        next.add(np);
                    }
                }
            }
            if (next.isEmpty())
                break;

            precalc.add(next);
            System.out.println("len=" + i);
            System.out.println("with " + next.size() + " permutations");
            System.out.println(next);
            current = next;
        }
    }

    /**
     * precalc contains sequences of different numbers.
     * => any extension of n -> n,n will create an unique solution.
     * 
     * the difference to current length defines how many combinations are insertable.
     */
    private void solve() {
        for (int in = 1;in <= 99;++in) {
            BigInteger wantedLen = new BigInteger(Integer.toString(in));
            BigInteger count = BigInteger.ZERO;
            for (ArrayList<P> pc : precalc) {
                P p = pc.get(0);
                int ik = p.list.size();
                if (ik > in)
                    break;
                
                BigInteger currentLen = new BigInteger(Integer.toString(ik));
                
                BigInteger k = wantedLen.subtract(currentLen);
                BigInteger n = currentLen;
                BigInteger addend = nOverK(n.add(k).subtract(BigInteger.ONE), n.subtract(BigInteger.ONE));
                
                BigInteger len = new BigInteger(Integer.toString(pc.size()));
                System.out.println(currentLen + " -> " + wantedLen + ": " + addend + " * " + len);
                count = count.add(addend.multiply(len));
            }
            System.out.println("Total permutations for " + in + " = " + count);
        }
    }

    /**
     * Helper to calc the faculty.
     * @param k a value
     * @return the faculty.
     */
    private BigInteger faculty(BigInteger k) {
        BigInteger r = BigInteger.ONE;
        while (k.compareTo(BigInteger.ONE) > 0) {
            r = r.multiply(k);
            k = k.subtract(BigInteger.ONE);
        }
        return r;
    }

    /**
     * Calculate n over k.
     * @param n 
     * @param k
     * @return ( n
     *           k )
     */
    private BigInteger nOverK(BigInteger n, BigInteger k) {
        BigInteger fn = faculty(n);
        BigInteger fk = faculty(k);
        BigInteger fnk = faculty(n.subtract(k));
        BigInteger r = fn.divide(fnk.multiply(fk));
        return r;
    }
}