0

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

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

我正在寻找一种同样美丽的方式，适用于任意 N。

位重新排序示例。8 个值：0..7用 3 位编码：000 – 111. 为了重新排序该集合，我存储了每个位的新位置。取一个数组[0,1,2]并随机重新排序，然后将结果存储为置换键。即将[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
4

3 回答 3

3

正如评论中所指出的，您对能够N!使用短键编码任意一种排列不感兴趣；您只是在寻找一种在给定短键的情况下确定性地选择 a 排列的方法。

我建议你需要做的就是

  • 选择你最喜欢的伪随机数生成器；
  • 用你已知的快捷键播种
  • 使用它从您的N项目列表中选择值
于 2015-07-29T09:03:35.097 回答
2

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

于 2015-07-29T07:30:44.713 回答
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 互质，如果不是，则拒绝或调整它。

于 2015-07-29T08:23:00.320 回答