什么函数伪随机地重新排序 N 个项目？

Question

有 1 到 N 的自然数（N 大约是 1e7），我梦想的函数会以某种方式重新排序集合，通过一组相当短的参数定义，与数值范围相比。

对于N = 2^i - 1，这可能只是位重新排序，因此，0..i 的一组仅 i 值定义了 突变。

我正在寻找一种类似漂亮的方式，适用于任意N。

位重排序示例。 8 个值：0..7 用 3 位编码：000 – 111。为了重新排序该集合，我存储了每一位的新位置。取一个数组 [0,1,2] 并对其随机重新排序，然后将结果存储为排列键。 IE。 [1,0,2] 将像这样重新排序 8 个值：

   210   201   
0: 000 - 000 :0
1: 001 - 010 :2
2: 010 - 001 :1
3: 011 - 011 :3
4: 100 - 100 :4
5: 101 - 110 :6
6: 110 - 101 :5
7: 111 - 111 :7

Answer 1

不太确定我是否理解你的问题，但你可以循环遍历 1..N 中的数字，对于每个步骤 i，生成一个 1..N 范围内的伪随机数 j，然后然后交换 i 和 j。

Answer 2

不消耗内存的简单方法是将每个数字乘以与N互质的常数，然后像这样计算除以N的余数（Java中的示例）：

static int reorder(int input, int N) {
    // 15485863 is prime, thus coprime with any lesser N
    return (int) ((input * 15485863L) % N);
}

使用 N = 10345560 进行测试：

public static void main(String[] args) {
    int N = 10345560;
    int[] source = IntStream.range(0, N).toArray();
    int[] reordered = IntStream.of(source).map(i -> reorder(i, N)).toArray();
    // Check that all reordered numbers are within 0..N-1
    assert IntStream.of(reordered).allMatch(i -> i >= 0 && i < N);
    // Check that all numbers are different
    assert IntStream.of(reordered).distinct().count() == N;
}

优点是你不需要中间内存来存储所有的数字：你可以以流的方式处理它们（例如，从一个文件读取并将结果写入另一个文件）。

缺点是对于提供的参数，您必须测试它是否与 N 互质，如果不是则拒绝或调整它。

Answer 3

如评论中所述，您对能够使用短密钥对 N! 排列中的任意一种进行编码不感兴趣；您只是在寻找一种方法来确定性地选择给定短键的排列。

我建议你只需要

选择你最喜欢的伪随机数生成器；
使用您已知的短密钥为它播种
使用它从您的 N 项列表中选择值

什么函数伪随机地重新排序 N 个项目？

What function pseudo-randomly reorders exactly N items?

algorithm

math

set

bijection