排列的数据转换

Question

我有一个方阵 MxN，元素为 x_ij。每个值都用于 some_function(i,j) 形式的函数。该函数按列顺序应用。我想要实现的是一个内核函数 k(i, j) ，它将被放置在 some_function:

def some_function(i, j):
   i', j' = k(i, j)

我将return另一组(i', j') 使(i'!=i, j'!=j) 和(i', j') 对应于初始方阵。应用于每个值 (i,j) 的函数不会产生任何重复的对。核函数 (i',j') 产生的数字应该是分布式的。

我的第一个想法是预先计算另一个列表中的排列并将该值传递给 some_function。我想知道是否有更好的方法来做到这一点。谢谢你。

Answer 1

将 MxN 矩阵视为长度为 M*N 的一维数组。您想要创建一个转换，将 0..MN-1 范围内的每个数字唯一地映射到该范围内的另一个数字（并在 MN 步骤 returns 之后映射到初始索引）。

实现此目标的最简单方法是使大小为 P 的步长与 M 和 N 互质且大于 M 示例：

indx = M * i + j  /start cell
for k = 0.. M*N - 1 do begin
  indx = (indx + P) % (M*N) //integer modulus
  i = indx / M  //integer division
  j = indx % M  //integer modulus
end // indx returns to the start value

for M=2,N=4, P=5
indx  i   j
0     0   0
5     2   1
2     1   0
7     3   1  
4     2   0
1     0   1
6     3   0
3     1   1

注意 i 和 j 每次都会改变。

排列的数据转换

Data transformation for permutation

algorithm

transformation