如何计算线性时间内的排列,扭曲

我在Java中有一个资源调度问题需要对事物进行排序,但是对于哪些资源可以彼此相邻存在限制.一个很好的类比是一串"数字",其中只有某些数字可以彼此相邻.我的解决方案是递归的,适用于小字符串,但运行时间是O(X ^ N),其中X是可能的数字(基数),N是字符串的长度.它很快变得无法管理.

使用下面的兼容性矩阵,以下是允许字符串的一些示例
长度为1:0,1,2,3,4
长度为2:02,03,14,20,30,41
长度为3:020,030, 141,202,203,302,303,414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

我计算所有长度为N的字符串的解决方案是从一个空字符串开始,置换第一个数字,并对所有长度为N-1的字符串进行递归调用.递归调用检查添加的最后一个数字,并尝试可以在该数字旁边的所有排列.有一些优化,所以我不会尝试每次都进行00,01,04,例如02,03,但是从基数5(示例)扩展到基数4000时,性能仍然很差.

除了试图列举所有排列之外,还有什么想法更好地计算排列？

如果你只想要一定长度的字符串数,你可以将兼容性矩阵与它自己相乘几次,并将它的值相加.

n = 字符串长度
A = 可能字符串的兼容性矩阵
数 = A ^{n -1的}总和

几个例子:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

原始矩阵(行i,列j)可以被认为是以符号i开始的字符串的数量,并且其下一个符号是符号j.或者,您可以将其视为长度为2的字符串数,以符号i开头,以符号j结尾.

矩阵乘法保留了这个不变量,因此在取幂后,A ^{n -1}将包含以符号i开头,长度为n,以符号j结尾的字符串数.

请参阅维基百科:通过平方算法来更快地计算矩阵幂.

(感谢stefan.ciobaca)

这个具体案例简化为公式:

可能的字符串的数目 = ˚F(Ñ)= 4 +Σ _{ķ = 1 .. Ñ} 2 ^{⌊ ķ -1/₂ ⌋} = ˚F(Ñ -1)+ 2 ^{⌊ Ñ -1/₂ ⌋}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66