0

我想为每个给定的and构造一个从到where和的双射函数。该函数实际上应该从 的随机排列中返回一个值。随机性由. 不同的可能对应不同的排列。我希望函数的时间复杂度是每个给定的。f(k, n, seed)[1,n][1,n]1<=k<=n1<=f(k, n, seed)<=nseedn1,2,...,nseedseedf(k, n, seed)O(1)1<=k<=nseed

任何人都知道我该如何构造这样的功能？允许随机性是伪随机性。n可以非常大（例如>= 1e8）。

4

2 回答 2

0

不管你怎么做，你总是必须存储一个仍然可用的号码列表或已经使用的号码......一个简单的可能性是以下

const avail = [1,2,3, ..., n];

let random = new Random(seed)

function f(k,n) {
  let index = random.next(n - k);
  let result = avail[index]
  avail[index] = avail[n-k];
}

对此的假设如下

  • 数组avail索引为 0
  • random.next(x)创建一个随机i整数0 <= i < x
  • 第一个k调用函数f的是0
  • f被要求连续k 0, 1, 2, 3, ..., n

原理如下：

avail保留所有仍可用于排列的数字。当您采用随机索引时，该索引处的元素是排列的下一个元素。然后，无需从数组中切出该元素，这非常昂贵，您只需将当前选择的元素替换为avail数组中的最后一个元素。在下一次迭代中，您（实际上）avail通过将随机数的上限减少 1 来将数组的大小减少 1。

我不确定这种随机排列在值分布方面的安全性如何，例如，某个范围的数字更有可能出现在排列的开头或排列的结尾.

于 2021-04-17T09:26:20.537 回答
0

一个简单但不是很“随机”的方法是使用这样一个事实：如果 a 与 n 互质（即它们没有公因数），那么

x-> (a*x + b)%n

是 {0,..n-1} 到 {0,..n-1} 的排列。要找到它的倒数，您可以使用扩展欧几里得算法来找到 k 和 l，以便

1 = gcd(a,n) = k*a+l*n

因为那么上面的地图的倒数是

y -> (k*x + c) mod n
where c = -k*b mod n

因此，您可以选择 a 作为 {0,..n-1} 中与 n 互质的“随机”数，并选择 b 作为 {0,..n-1} 中的任意数

请注意，您需要在 64 位算术中执行此操作以避免计算 a*x 时溢出。

于 2021-04-17T11:18:41.717 回答