2

我想以非顺序方式遍历集合 Q = [0, 2^16) 中的所有元素。为此，我需要一个函数 f(x) Q --> Q，它给出了对集合进行排序的顺序。例如：

f(0) = 2345   
f(1) = 4364   
f(2) = 24   
(...)

为了恢复顺序，我需要反函数 f'(x) Q --> Q ，它将输出：

f(2345) = 0
f(4364) = 1
f(24) = 2
(...)

该函数必须是双射的，对于 Q 的每个元素，该函数唯一地映射到 Q 的另一个元素。

我怎样才能生成这样的功能，或者是否有任何已知的功能可以做到这一点？

4

2 回答 2

4

编辑：在下面的答案中，f(x)是“x 之后的内容”，而不是“x 位置的内容”。例如，如果您的第一个数字是 5，则 f(5) 是下一个元素，而不是 f(1)。回想起来，您可能认为 f(x) 是“位置 x 中的内容”。如果用作“位置 x 中的内容”，则此答案中定义的函数要弱得多。

线性同余生成器满足您的需求。

线性同余生成器由等式定义

f(x) = a*x+c (mod m)

对于一些常数a, c, 和m. 在这种情况下，m = 65536。

如果以下属性成立，则 LCG 具有完整期限（您想要的属性）：

  1. c并且m是相对优质的。
  2. a-1能被 的所有素因数整除m。
  3. 如果m是4的倍数，a-1就是4的倍数。

我们会和a = 5,一起去c = 1。

f(x)为了反转 LCG，我们根据 来求解x：

x = (a^-1)*(f(x) - c) (mod m)

我们可以通过扩展欧几里得算法找到 5 mod 65536 的倒数，或者由于我们只需要这一计算，我们可以将其插入 Wolfram Alpha. 结果是 52429。

因此，我们有

f(x) = (5*x + 1) % 65536
f^-1(x) = (52429 * (x - 1)) % 65536
于 2014-07-14T04:54:57.743 回答
0

有很多方法可以解决这个问题。

由于您的集合大小很小，因此可以简单地通过内存查找来完成生成函数及其逆的要求。因此，一旦您选择了排列，您就可以将正向和反向存储在查找表中。

创建排列的一种方法是映射出数组中的所有元素，然后随机交换它们“足够”的次数。C代码：

int f[PERM_SIZE], inv_f[PERM_SIZE];
int i;

// start out with identity permutation
for (i=0; i < PERM_SIZE; ++i) {
    f[i] = i;
    inv_f[i] = i;
}

// seed your random number generator
srand(SEED);

// look "enough" times, where we choose "enough" = size of array
for (i=0; i < PERM_SIZE; ++i) {
    int j, k;
    j = rand()%PERM_SIZE;
    k = rand()%PERM_SIZE;
    swap( &f[i], &f[j] );
}

// create inverse of f
for (i=0; i < PERM_SIZE; ++i)
    inv_f[f[i]] = i;

享受

于 2014-07-14T04:21:54.623 回答