一次选择一个数字，介于 0 到 100 亿之间，随机顺序

Question

>问题

我需要一次在 0 到 10,000,000,000 之间选择一个唯一的随机数，并一直这样做，直到选择了所有数字。从本质上讲，我需要的行为是一个预先构建的堆栈/队列，其中有 100 亿个随机顺序的数字，无法将新项目推送到其中。

不太好的解决方法：

我的大脑中不乏低效的方法。如

保留生成的数字

• 并检查新生成的随机数是否已使用，在某些时候，这会让我们在生成可用数字之前无限期等待。
• 将所有可能的数字保留在表中并弹出随机行并维护新的行计数以供下一次选择等。不确定这是好是坏。

问题：

1. 除了存储所有可能的组合和使用随机之外，还有其他确定性方法吗？

   • 就像维护可用数字的窗口并首先随机选择一个窗口，然后在该窗口中随机选择一个数字等，例如：像这样

2. 如果不是，在相当小的空间中存储数字的最佳类型是什么？

   • 50+%的数字不适合32位(整数)，64位(长)是浪费。Cos 最大数字适合 34 位，每个数字浪费 30 位(总共>37GB)。

如果这个问题还没有解决。

3. 什么是存储和挑选随机点并快速调整结构以使下一次拣选快速的良好数据结构？

很抱歉模棱两可。最大可选数为 9,999,999,999，最小可选数为 1。

Answer 1

你问："除了存储所有可能的组合和使用随机之外，还有其他确定性的方法吗？

是的，有：加密。 使用给定密钥进行加密可确保唯一输入的唯一结果，因为它是可逆的。 每个键定义可能输入的一对一排列。 您需要对 [1..10e9] 范围内的输入进行加密。 要处理这么大的事情，您需要 34 位数字，最高可达 17,179,869,183。

没有标准的 34 位加密。 根据您需要多少安全性以及您需要数字的速度，您可以编写自己的简单，快速，不安全的四轮Feistel密码，或者对于更慢，更安全的东西，请使用34位模式下的Hasty Pudding密码。

使用任一解决方案，如果第一次加密给出的结果超出范围，只需再次加密结果，直到新结果在所需范围内。 一对一属性可确保加密链的最终结果是唯一的。

要生成一系列独特的随机数字，只需加密 0、1、2、3、4、...顺序使用相同的密钥。 加密保证该密钥的结果是唯一的。 如果您记录了自己已经走了多远，那么以后可以生成更多唯一数字，最高可达 100 亿个限制。

Answer 2

正如AChampion在评论中提到的，你可以使用线性同余生成器。

您的模数 (m) 值将为 100 亿。为了获得一个完整的周期(该范围内的所有值都出现在序列重复之前)，您需要选择 a 和 c 常量以满足某些条件。M 和 C 需要是相对素数，A - 1 需要被 m 的素因数(只有 2 和 5)和 4(因为 100 亿可以被 4 整除)整除。

如果你只提出一组常量，你将只有一个可能的序列，并且数字将始终以相同的顺序出现。但是，您可以轻松地随机生成满足条件的常量。要检验 c 和 m 的相对素数，只需检验 c 是否可以被 2 和 5 整除，因为这些是 m 的唯一素因数(请参阅此处共质性检验的第一个条件)

Python中的简单草图：

import random
m = 10000000000
a = 0
c = 0
r = 0
def setupLCG():
global a, c, r
# choose value of c that is 0 < c < m and relatively prime to m
c = 5
while ((c % 5 == 0) or (c % 2 == 0)):
c = random.randint(1, m - 1)
# choose value of a that is 0 < a <= m and a - 1 is divisible by
# prime factors of m, and 4
a = 4
while ((((a - 1) % 4) != 0) or (((a - 1) % 5) != 0)):
a = random.randint(1, m)
r = random.randint(0, m - 1)
def rand():
global m, a, c, r
r = (a*r + c) % m
return r
random.seed()
setupLCG()
for i in range(1000):    
print rand() + 1

这种方法不会给出10000000000！可能的组合的全部可能性，但它仍然会在10¹⁹的数量级，这是相当多的。它确实有一些其他问题(例如，偶数值和奇数值的交替)。你可以通过一个小的数字池来混合它，每次从序列中添加一个数字，然后随机抽出一个。

Answer 3

与 rossum 的建议类似，您可以使用可逆整数哈希函数，该函数将 [0,2^k) 中的一个整数唯一映射到同一范围内的另一个整数。对于您的特定问题，您选择 k=34 (2^34=160 亿)并拒绝任何超过 100 亿的数字。下面是一个完整的实现：

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
uint64_t hash_64(uint64_t key, uint64_t mask)
{
key = (~key + (key << 21)) & mask; // key = (key << 21) - key - 1;
key = key ^ key >> 24;
key = ((key + (key << 3)) + (key << 8)) & mask; // key * 265
key = key ^ key >> 14;
key = ((key + (key << 2)) + (key << 4)) & mask; // key * 21
key = key ^ key >> 28;
key = (key + (key << 31)) & mask;
return key;
}
int main(int argc, char *argv[])
{
uint64_t i, shift, mask, max = 10000ULL;
char *dummy;
if (argc > 1) max = strtol(argv[1], &dummy, 10);
for (shift = 0; 1ULL<<shift <= max; ++shift) {}
mask = (1ULL<<shift) - 1;
for (i = 0; i <= mask; ++i) {
uint64_t x = hash_64(i, mask);
x = hash_64(x, mask);
x = hash_64(x, mask); // apply multiple times to increase randomness
if (x > max || x == 0) continue;
printf("%llun", x);
}
return 0;
}

这应该以随机顺序为您提供数字 [0,10000000000

]。

Answer 4

对于范围1-999,999,999,999等效于0-999,999,999,998(只需添加1)。给定LCG的定义，那么您可以实现这一点：

import functools as ft
import itertools as it
import operator as op
from sympy import primefactors, nextprime
def LCG(m, seed=0):
factors = set(primefactors(m))
a = ft.reduce(op.mul, factors)+1
assert(m%4 != 0 or (m%4 == 0 and (a-1)%m == 0))
c = nextprime(max(factors)+1)
assert(c < m)
x = seed
while True:
x = (a * x + c) % m
yield x
# Check the first 10,000,000 for duplicates
>>> x = list(it.islice(LCG(999999999999), 10000000))
>>> len(x) == len(set(x))
True
# Last 10 numbers
>>> x[-10:]
[99069910838, 876847698522, 765736597318, 99069940559, 210181061577,
432403293706, 99069970280, 543514424631, 99069990094, 99070000001]

对于这个问题的上下文，我采取了一些快捷方式，因为assert应该替换为处理代码，目前如果这些assertFalse，它就会失败

Answer 5

我不知道有任何真正随机的方法可以在不存储已选择的数字列表的情况下选择数字。 你可以做某种线性哈希算法，然后通过它传递数字 0 到 n(当你的哈希返回高于 10000000000 的值时重复)，但这不会是真正的随机。

如果要存储数字，可以考虑通过位掩码进行存储。 为了在位掩码中快速选取，您可能会保留一棵树，其中每个叶子将表示相应 32 个字节中的可用位数，上面的分支将列出相应 2K 条目中的可用位数，依此类推。 然后你有 O(log(n)) 时间来查找下一个条目，以及 O(log(n)) 时间来声明一点(因为您必须更新树)。 它还需要存储 2n 位左右的东西。

Answer 6

您绝对不需要存储所有数字。

如果你想要一组从1到10B的完美数字，每个数字恰好一次，我看到有两个选项：正如其他人所暗示的那样，使用34位LCG或Galois LFSR或XOR-shift，生成从1到17B左右的数字序列，然后扔掉超过10B的数字。我不知道有任何特定的 34 位功能，但我确信有人是。

选项 2，如果您可以腾出 1.25 GB 的内存，是创建一个位图，仅存储已选择某个数字的信息，然后使用 Floyd 算法获取数字，这将很快并为您提供质量更好的数字(事实上，它可以很好地与硬件 RNG 一起使用)。

选项 3，如果您可以忍受罕见但偶尔出现的错误(重复或从未选择的数字)，请将位图替换为布隆滤镜并节省内存。

Answer 7

如果可预测性不是问题，则可以使用 XOR 操作快速生成。假设您要生成一个具有 n 位(在您的例子中为 34)的唯一数字的随机序列：

1-在n位上取种子数。K，可以将此数字视为每次运行新实验时可以更改的种子。

2-使用从0向上的计数器

3-每次XOR计数器与K：next = counter xor K; counter++;

要将范围限制为 100 亿，这不是 2 的幂，您需要进行拒绝。

明显的缺点是可预测性。在步骤 3 中，您可以对计数器的字节进行先验转置，例如反转字节顺序(例如从小端序转换为大端序时)。这将对下一个数字的可预测性产生一些改进。

最后，我不得不承认，这个答案可以被认为是@rossum答案中提到的加密的特定实现，但它更具体，可能是最快的。

Answer 8

非常慢，但它应该可以工作。完全随机

using System;
using System.Diagnostics;
using System.IO;
using System.Runtime.InteropServices;
namespace ConsoleApplication1
{
class Program
{
static Random random = new Random();
static void Main()
{
const long start = 1;
const long NumData = 10000000000;
const long RandomNess = NumData;
var sz = Marshal.SizeOf(typeof(long));
var numBytes = NumData * sz;
var filePath = Path.GetTempFileName();
using (var stream = new FileStream(filePath, FileMode.Create))
{
// create file with numbers in order
stream.Seek(0, SeekOrigin.Begin);
for (var index = start; index < NumData; index++)
{
var bytes = BitConverter.GetBytes(index);
stream.Write(bytes, 0, sz);
}
for (var iteration = 0L; iteration < RandomNess; iteration++)
{
// get 2 random longs
var item1Index = LongRandom(0, NumData - 1, random);
var item2Index = LongRandom(0, NumData - 1, random);

// allocate room for data
var data1ByteArray = new byte[sz];
var data2ByteArray = new byte[sz];
// read the first value
stream.Seek(item1Index * sz, SeekOrigin.Begin);
stream.Read(data1ByteArray, 0, sz);
// read the second value
stream.Seek(item2Index * sz, SeekOrigin.Begin);
stream.Read(data2ByteArray, 0, sz);
var item1 = BitConverter.ToInt64(data1ByteArray, 0);
var item2 = BitConverter.ToInt64(data2ByteArray, 0);
Debug.Assert(item1 < NumData);
Debug.Assert(item2 < NumData);
// swap the values
stream.Seek(item1Index * sz, SeekOrigin.Begin);
stream.Write(data2ByteArray, 0, sz);
stream.Seek(item2Index * sz, SeekOrigin.Begin);
stream.Write(data1ByteArray, 0, sz);
}
}
File.Delete(filePath);
Console.WriteLine($"{numBytes}");
}
static long LongRandom(long min, long max, Random rand)
{
long result = rand.Next((int)(min >> 32), (int)(max >> 32));
result = (result << 32);
result = result | rand.Next((int)min, (int)max);
return result;
}
}
}