arrays - 一维生命游戏的非迭代算法

Question

考虑一个 bool 数组 a[n] ，其中每个元素都是一个单元格。如果一个且只有一个相邻细胞存活，则该细胞在下一代中存活(设置为 true )，否则它死亡(设置为 false )。第一个和最后一个单元格被认为是邻居。

给定a[n] , 数组大小 n , 和一个正整数 t , 我想计算 a[n]在第 t 代进化之后，但未在 t 上使用任何迭代算法，这可能非常大。

我观察到的:如果我们定义 S_k(a[n])是 a[n] 的循环移位在k的右边元素。即 a[0]变成 a[k]一类后如果0 <= k < n .定义 a[n] ^ b[n]是两个 bool 数组之间的逐元素异或运算。如果w[n]是一个 bool 数组，下一代可以表示为

r(w[n]) = S_{-1}(w[n]) ^ S_1(w[n])

异或运算符 ^是结合的和交换的。使用此属性，接下来的几代 w[n]可以通过计算

r^2(w[n]) = ( S_{-2}(w[n]) ^ S_0(w[n]) ) ^ ( S_0(w[n]) ^ S_2(w[n]) )
          = S_{-2}(w[n]) ^ S_2(w[n])

如果我们让 s_j = S_{-j}(w[n]) ^ S_j(w[n]) , 有规律

r(w[n]) = s_1
r^2(w[n]) = s_2
r^3(w[n]) = s_3 ^ s_1
r^4(w[n]) = s_4
...
r(s_m) = s_{m-1} ^ s_{m+1}

此外，s_n = 0 (零数组)因为完整的循环移位是原始数组。我如何使用它来导出 r^t(w[n]) 的非迭代表达式？

编辑:模式是

[1]
[2]
[1,3]
[4]
[3,5]
[2,6]
[1,3,5,7]
[8]

Answer 1

让我们将您的输入表示为列向量 a_0，大小为 n 的 Z/2Z 元素。

您可以使用矩阵乘法计算下一代向量 a_1:

a_1 = M.a_0 = |0 1 0 0 ... 0 0 0|  |a_01|
              |1 0 1 0 ... 0 0 0|  |a_02|
              |0 1 0 1 ... 0 0 0|  |a_03|
              ....
              |0 0 0 0 ... 0 1 0|  |... |
              |0 0 0 0 ... 1 0 1|  |... |
              |0 0 0 0 ... 0 1 0|  |a_0n|

鉴于此递归关系，您可以使用以下公式计算时间 t 的生成:

a_t = M^t . a_0

并且您可以使用重复平方在 O(n^3.log(t)) 中轻松计算 M^t。