如何在 KDB 中遍历 M*N 网格

Question

如何在Qlang中遍历m*n网格，您可以向上，向下或对角线遍历。以查找可以到达终点的可能方式。

像下面这样：

                  0
                  |
           ------- ------
          |       |       |
      ( 0 1)    (1 1)         (1 0) 
         |         .          |
   ------ -----            ------ -----
  |            |   .      |            |
( 0 1)        (1 0)       ( 1 1)        (2 0)   
.... 
(2 2)        .....................   (2 2)

Answer 1

一种方法是

使用 .z.s 递归调用具有不同参数的初始函数，并求和以给出路径总数。

f:{
  // When you reach a wall, there is only one way to corner so return valid path
  if[any 1=(x;y);:1];
  // Otherwise spawn 3 paths - one up, one right and one diagonally
  :.z.s[x-1;y] + .z.s[x;y-1] + .z.s[x-1;y-1] 
}
q)f[2;2]
3
q)f[2;3]
5
q)f[3;3]
13

如果您沿着边缘而不是正方形移动，您可以将第一行更改为：

if[any 0=(x;y);:1];

封闭式解决方案只是找到Delannoy数，当您沿着边缘行驶时，可以实现这样的数字。

d:{
  k:1+min(x;y);
  f:{prd 1+til x};
  comb:{[f;m;n] f[m] div f[n]*f[m-n]}[f];
  (sum/) (2 xexp til k) * prd (x;y) comb/:: til k
 }
q)d[3;3]
63f

对于较大的电路板来说，这要快得多，因为我认为第一个解决方案的复杂性是 O（3^m+n），而第二个解决方案的复杂性是 O（m*n）

q)t f[7;7]
13
q)t f[10;10]
1924
q)t d[7;7]
0
q)t d[100;100]
1