用于存储消息的确定性和可逆排列函数

Question

我想通过更改行的顺序来隐藏 csv 文件的列中的秘密消息。

我正在寻找一个确定性且可逆的排列函数。

假设我有按字典顺序排列的行列表 A=[1,2,3,4,5] 。我有5个！= 120 种可能的排列。这意味着我可以保存 6 位消息，因为 2^6 = 64 < 120。

我想要以下函数进行编码和解码。

A = [1,2,3,4,5]
message = '010010'

B = encode(A, message) # [2,1,3,4,5] for example

B = [2,1,3,4,5]
message = decode(B) # get back message

我可以计算所有排列，但如果有很多行，那就需要很长时间。该函数必须处理大量行，例如 10 000 行。因此，如果您有任何建议，我在这里寻求帮助。

Answer 1

这是一种在线性时间内在排列和排名之间进行转换的算法。然而，它使用的排名不是字典顺序的。这很奇怪，但却是一致的。我将给出两个函数，一个将排名转换为排列，另一个则执行相反的操作。

\n

首先，取消排名（从排名到排列）

\n

Initialize:\nn = length(permutation)\nr = desired rank\np = identity permutation of n elements [0, 1, ..., n]\n\nunrank(n, r, p)\n  if n > 0 then\n    swap(p[n-1], p[r mod n])\n    unrank(n-1, floor(r/n), p)\n  fi\nend\n

\n

接下来，进行排名：

\n

Initialize:\np = input permutation\nq = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)\nn = length(p)\n\nrank(n, p, q)\n  if n=1 then return 0 fi\n  s = p[n-1]\n  swap(p[n-1], p[q[n-1]])\n  swap(q[s], q[n-1])\n  return s + n * rank(n-1, p, q)\nend\n

\n

两者的运行时间均为 O(n)。

\n

有一篇很好读的论文解释了为什么这样做：线性时间中的排名和取消排名排列，作者：Myrvold 和 Ruskey，《信息处理快报》第 79 卷，第 6 期，2001 年 9 月 30 日，第 281\xe2\x80\x93284 页。

\n

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

\n