arrays - 仅使用 3 个元素形成数组的方法有多少？

Question

我们需要找出可以形成仅包含 3 个元素(1,2 和 3)的 N 长度数组(A)的方法数量。
数组的 的方式几乎没有限制。相邻元素 可以放在数组中:
相邻元素对数(A[i], A[i + 1])某种类型的不能超过问题陈述中给出的。

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

对于 类型的相邻元素A[i] == A[i + 1] ，它们可以在数组中出现任意次数

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

案例:

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

伪代码解释:
我尝试使用 来解决这个问题递归 (蛮力)，即在 每个函数调用 插入任何元素(1,2,3)在索引 i并检查 (A[i - 1], A[i])对没有超过问题陈述中给出的限制，如果 是的然后 return否则 继续调用 func()而i != n .
这种方法很好，但它给出了 TLE(超出时间限制)错误，因此它不是找出形成数组的方法数量的最佳方法。

Is there any other efficient way to solve this problem ?

Answer 1

我会采取的方法不是创建实际的数组。相反，我会通过分析您的限制来解决它。

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

因此，您的系统中只允许进行有限数量的转换。
所以我的出发点是计算所有可能的转换组合，每个组合都有一个最小长度 n 。这可以使用一些蛮力方法来执行，尽管可能有也可能没有更有效的方法。
蛮力方法产生的输出样本应如下所示...

最小长度 2 个过渡:

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

最小长度 3 个转换:

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.

一旦我们计算了每个最小长度的所有可能组合计数，我们就根据实际输入 n 执行排列数学。我们可以重用我们创建的原始结构来非常快速地执行 n 的多个输入的计算。
例如，当 n = 3 时，我们从 3 开始进行空转换。然后我们添加 8 以获得不需要最小长度 n 的转换的排列。然后我们计算最小长度 n - 1、n - 2 等的排列，直到 n - x = 2。排列是通过用多余空间移动每个过渡的位置来计算的。即其中 n = 3 和 min-n = 2，多余空间 = 1，所以我们可以将转换左/右移动 1，给我们 2 个模式而不是 1。所以因为有 5 个模式的长度为 2，并且每个都可以转换为 2 种模式，这将给我们 10 种模式。所以我们有 10 + 8 + 3 = 21。
为了进一步阐明数学，我将在 n-3 模式上使用 n = 10。我们有 9 个转换槽和 2 个转换，并且可以应用置换数学:

第一个转换可能发生在 9 个转换槽的前 8 个中的任何位置。选择哪个插槽决定了第二个转换可能会去哪里，但现在让我们忽略它。然后这变成 9!/7!。但是，这包括所有无序组合，因此我们希望将其进一步除以 2!。所以我们有 9 * 4 = 36 种组合，* n-3 模式的模式计数 = 36 * 8。将其添加到 n-2 模式、n-4 模式等...

这可以概括为:

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