从非常大的集合中生成看似随机排列而不重复的有效方法？
Efficient way to generate a seemingly random permutation from a very large set without repeating?
我有一个非常大的集合（十亿 或更多，预计会呈指数增长到某种程度），我想从中生成看似随机的元素而不重复。我知道我可以选择一个随机数并重复并记录我生成的元素，但是随着生成数字，这会占用越来越多的内存，并且在输出几百万个元素后就不实用了。
我的意思是，我可以说 1、2、3 最多十亿，并且 每个都是常数时间而无需记住之前的所有内容，或者我可以说 1、3、5 ,7,9 然后是 2,4,6,8,10，但是是否有更复杂的方法来做到这一点并最终得到该集合的看似随机排列？
更新
1、集合在生成过程中不改变大小。我的意思是当用户的输入线性增加时，集合的大小呈指数增加。
2、简而言之，集合就是1到100亿以上的每一个整数的集合。
3、总之，上百亿是因为每个元素都携带了很多独立选择的信息，比如。想象一个 RPG 角色有 10 个属性，每个属性可以从 1 到 100（对于我的问题，不同的选择可以有不同的范围），因此有 10^20 个可能的字符，数字“10873456879326587345”将对应一个具有“11， 88、35...”，我想要一种算法来一个一个地生成它们而不重复，但让它 看起来 随机。
我会使用随机数并将其与集合开头的元素交换。
这是一些伪代码
set = [1, 2, 3, 4, 5, 6]
picked = 0
Function PickNext(set, picked)
If picked > Len(set) - 1 Then
Return Nothing
End If
// random number between picked (inclusive) and length (exclusive)
r = RandomInt(picked, Len(set))
// swap the picked element to the beginning of the set
result = set[r]
set[r] = set[picked]
set[picked] = result
// update picked
picked++
// return your next random element
Return temp
End Function
每次您选择一个元素时，都会进行一次交换，唯一使用的额外内存是 picked 变量。如果元素在数据库或内存中，则可能发生交换。
编辑 这是一个有效实现的 jsfiddle http://jsfiddle.net/sun8rw4d/
JavaScript
var set = [];
set.picked = 0;
function pickNext(set) {
if(set.picked > set.length - 1) { return null; }
var r = set.picked + Math.floor(Math.random() * (set.length - set.picked));
var result = set[r];
set[r] = set[set.picked];
set[set.picked] = result;
set.picked++;
return result;
}
// testing
for(var i=0; i<100; i++) {
set.push(i);
}
while(pickNext(set) !== null) { }
document.body.innerHTML += set.toString();
EDIT 2 最后，该集合的随机二进制游走。这可以通过 O(Log2(N)) 堆栈 space （内存）来完成，对于 100 亿只有 33。不涉及改组或交换。使用三进制而不是二进制可能会产生更好的伪随机结果。
// on the fly set generator
var count = 0;
var maxValue = 64;
function nextElement() {
// restart the generation
if(count == maxValue) {
count = 0;
}
return count++;
}
// code to pseudo randomly select elements
var current = 0;
var stack = [0, maxValue - 1];
function randomBinaryWalk() {
if(stack.length == 0) { return null; }
var high = stack.pop();
var low = stack.pop();
var mid = ((high + low) / 2) | 0;
// pseudo randomly choose the next path
if(Math.random() > 0.5) {
if(low <= mid - 1) {
stack.push(low);
stack.push(mid - 1);
}
if(mid + 1 <= high) {
stack.push(mid + 1);
stack.push(high);
}
} else {
if(mid + 1 <= high) {
stack.push(mid + 1);
stack.push(high);
}
if(low <= mid - 1) {
stack.push(low);
stack.push(mid - 1);
}
}
// how many elements to skip
var toMid = (current < mid ? mid - current : (maxValue - current) + mid);
// skip elements
for(var i = 0; i < toMid - 1; i++) {
nextElement();
}
current = mid;
// get result
return nextElement();
}
// test
var result;
var list = [];
do {
result = randomBinaryWalk();
list.push(result);
} while(result !== null);
document.body.innerHTML += '<br/>' + list.toString();
这是使用一小组 64 个元素运行几次的结果。 JSFiddle http://jsfiddle.net/yooLjtgu/
30,46,38,34,36,35,37,32,33,31,42,40,41,39,44,45,43,54,50,52,53,51,48,47,49,58,60,59,61,62,56,57,55,14,22,18,20,19,21,16,15,17,26,28,29,27,24,25,23,6,2,4,5,3,0,1,63,10,8,7,9,12,11,13
30,14,22,18,16,15,17,20,19,21,26,28,29,27,24,23,25,6,10,8,7,9,12,13,11,2,0,63,1,4,5,3,46,38,42,44,45,43,40,41,39,34,36,35,37,32,31,33,54,58,56,55,57,60,59,61,62,50,48,49,47,52,51,53
正如我在评论中提到的，除非你有一个有效的方法来 跳过 到你的 "on the fly" 集合中的特定点，否则这不会很高效。
如果它是可枚举的，那么使用调整到周期 0 .. 2^n - 1 的伪随机整数生成器，其中上限刚好大于你的集合的大小，并生成伪随机整数并丢弃那些超过你的集合的大小。使用这些整数为您的集合中的项目编制索引。
预先为自己计算一系列索引（例如在文件中），这些索引具有您需要的属性，然后为您的枚举随机选择一个起始索引，并以循环方式使用该系列。
您预先计算的序列的长度应 > 集的最大大小。
如果您将此（取决于您的编程语言等）与文件映射相结合，您的最终 nextIndex(INOUT state) 函数（几乎）与 return mappedIndices[state++ % PERIOD]; 一样简单，如果您有固定大小的每个条目（例如 8 个字节 -> uint64_t）。
当然，返回值可以>您当前设置的大小。简单地绘制索引，直到你得到一个<=你的设置当前大小。
更新（回应更新问题）：
如果要在您的 RPG 中创建 100 亿个唯一字符，还有另一种方法可以实现您的目标：生成一个 GUID 并为自己编写一个函数，该函数根据 GUID 计算您的数字。 man uuid 如果您使用的是 unix 系统。否则 google 它。 uuid 的某些部分不是随机的但包含元信息，某些部分是系统的（例如您的网卡 MAC 地址）或随机的，具体取决于生成器算法。但它们非常非常有可能是独一无二的。因此，每当您需要一个新的唯一编号时，请生成一个 uuid 并通过某种算法将其转换为您的编号，该算法基本上以非平凡的方式将 uuid 字节映射到您的编号（例如使用哈希函数）。
感谢您提出有趣的问题。您可以使用模幂创建具有几个字节的 "pseudorandom"*（循环）排列。假设我们有 n 个元素。搜索大于 n+1 的素数 p。然后找到原根 g 模 p。基本上根据原根的定义，动作 x --> (g * x) % p 是 {1, ..., p-1} 的循环排列。所以 x --> ((g * (x+1))%p) - 1 是 {0, ..., p-2} 的循环排列。如果它给出的值大于（或等于）n，我们可以通过重复先前的排列来获得 {0, ..., n-1} 的循环排列。
我将这个想法实现为一个 Go 包。 https://github.com/bwesterb/powercycle
package main
import (
"fmt"
"github.com/bwesterb/powercycle"
)
func main() {
var x uint64
cycle := powercycle.New(10)
for i := 0; i < 10; i++ {
fmt.Println(x)
x = cycle.Apply(x)
}
}
这输出类似
0
6
4
1
2
9
3
5
8
7
但这可能会有所不同，具体取决于所选的发电机。
它很快，但不是超快：在我 5 岁的 i7 上，计算 1000000000000000 个元素上的一个循环应用程序需要不到 210ns。更多详情：
BenchmarkNew10-8 1000000 1328 ns/op
BenchmarkNew1000-8 500000 2566 ns/op
BenchmarkNew1000000-8 50000 25893 ns/op
BenchmarkNew1000000000-8 200000 7589 ns/op
BenchmarkNew1000000000000-8 2000 648785 ns/op
BenchmarkApply10-8 10000000 170 ns/op
BenchmarkApply1000-8 10000000 173 ns/op
BenchmarkApply1000000-8 10000000 172 ns/op
BenchmarkApply1000000000-8 10000000 169 ns/op
BenchmarkApply1000000000000-8 10000000 201 ns/op
BenchmarkApply1000000000000000-8 10000000 204 ns/op
为什么我说"pseudorandom"？好吧，我们总是在创建一种非常特殊的循环：即使用模幂的循环。不过它看起来很伪随机。
我有一个非常大的集合（十亿 或更多，预计会呈指数增长到某种程度），我想从中生成看似随机的元素而不重复。我知道我可以选择一个随机数并重复并记录我生成的元素，但是随着生成数字，这会占用越来越多的内存，并且在输出几百万个元素后就不实用了。
我的意思是，我可以说 1、2、3 最多十亿，并且 每个都是常数时间而无需记住之前的所有内容，或者我可以说 1、3、5 ,7,9 然后是 2,4,6,8,10，但是是否有更复杂的方法来做到这一点并最终得到该集合的看似随机排列？
更新
1、集合在生成过程中不改变大小。我的意思是当用户的输入线性增加时，集合的大小呈指数增加。
2、简而言之，集合就是1到100亿以上的每一个整数的集合。
3、总之，上百亿是因为每个元素都携带了很多独立选择的信息，比如。想象一个 RPG 角色有 10 个属性，每个属性可以从 1 到 100（对于我的问题，不同的选择可以有不同的范围），因此有 10^20 个可能的字符，数字“10873456879326587345”将对应一个具有“11， 88、35...”，我想要一种算法来一个一个地生成它们而不重复，但让它 看起来 随机。
我会使用随机数并将其与集合开头的元素交换。
这是一些伪代码
set = [1, 2, 3, 4, 5, 6]
picked = 0
Function PickNext(set, picked)
If picked > Len(set) - 1 Then
Return Nothing
End If
// random number between picked (inclusive) and length (exclusive)
r = RandomInt(picked, Len(set))
// swap the picked element to the beginning of the set
result = set[r]
set[r] = set[picked]
set[picked] = result
// update picked
picked++
// return your next random element
Return temp
End Function
每次您选择一个元素时，都会进行一次交换，唯一使用的额外内存是 picked 变量。如果元素在数据库或内存中，则可能发生交换。
编辑 这是一个有效实现的 jsfiddle http://jsfiddle.net/sun8rw4d/
JavaScript
var set = [];
set.picked = 0;
function pickNext(set) {
if(set.picked > set.length - 1) { return null; }
var r = set.picked + Math.floor(Math.random() * (set.length - set.picked));
var result = set[r];
set[r] = set[set.picked];
set[set.picked] = result;
set.picked++;
return result;
}
// testing
for(var i=0; i<100; i++) {
set.push(i);
}
while(pickNext(set) !== null) { }
document.body.innerHTML += set.toString();
EDIT 2 最后，该集合的随机二进制游走。这可以通过 O(Log2(N)) 堆栈 space （内存）来完成，对于 100 亿只有 33。不涉及改组或交换。使用三进制而不是二进制可能会产生更好的伪随机结果。
// on the fly set generator
var count = 0;
var maxValue = 64;
function nextElement() {
// restart the generation
if(count == maxValue) {
count = 0;
}
return count++;
}
// code to pseudo randomly select elements
var current = 0;
var stack = [0, maxValue - 1];
function randomBinaryWalk() {
if(stack.length == 0) { return null; }
var high = stack.pop();
var low = stack.pop();
var mid = ((high + low) / 2) | 0;
// pseudo randomly choose the next path
if(Math.random() > 0.5) {
if(low <= mid - 1) {
stack.push(low);
stack.push(mid - 1);
}
if(mid + 1 <= high) {
stack.push(mid + 1);
stack.push(high);
}
} else {
if(mid + 1 <= high) {
stack.push(mid + 1);
stack.push(high);
}
if(low <= mid - 1) {
stack.push(low);
stack.push(mid - 1);
}
}
// how many elements to skip
var toMid = (current < mid ? mid - current : (maxValue - current) + mid);
// skip elements
for(var i = 0; i < toMid - 1; i++) {
nextElement();
}
current = mid;
// get result
return nextElement();
}
// test
var result;
var list = [];
do {
result = randomBinaryWalk();
list.push(result);
} while(result !== null);
document.body.innerHTML += '<br/>' + list.toString();
这是使用一小组 64 个元素运行几次的结果。 JSFiddle http://jsfiddle.net/yooLjtgu/
30,46,38,34,36,35,37,32,33,31,42,40,41,39,44,45,43,54,50,52,53,51,48,47,49,58,60,59,61,62,56,57,55,14,22,18,20,19,21,16,15,17,26,28,29,27,24,25,23,6,2,4,5,3,0,1,63,10,8,7,9,12,11,13
30,14,22,18,16,15,17,20,19,21,26,28,29,27,24,23,25,6,10,8,7,9,12,13,11,2,0,63,1,4,5,3,46,38,42,44,45,43,40,41,39,34,36,35,37,32,31,33,54,58,56,55,57,60,59,61,62,50,48,49,47,52,51,53
正如我在评论中提到的，除非你有一个有效的方法来 跳过 到你的 "on the fly" 集合中的特定点，否则这不会很高效。
如果它是可枚举的，那么使用调整到周期 0 .. 2^n - 1 的伪随机整数生成器，其中上限刚好大于你的集合的大小，并生成伪随机整数并丢弃那些超过你的集合的大小。使用这些整数为您的集合中的项目编制索引。
预先为自己计算一系列索引（例如在文件中），这些索引具有您需要的属性，然后为您的枚举随机选择一个起始索引，并以循环方式使用该系列。
您预先计算的序列的长度应 > 集的最大大小。
如果您将此（取决于您的编程语言等）与文件映射相结合，您的最终 nextIndex(INOUT state) 函数（几乎）与 return mappedIndices[state++ % PERIOD]; 一样简单，如果您有固定大小的每个条目（例如 8 个字节 -> uint64_t）。
当然，返回值可以>您当前设置的大小。简单地绘制索引，直到你得到一个<=你的设置当前大小。
更新（回应更新问题）：
如果要在您的 RPG 中创建 100 亿个唯一字符，还有另一种方法可以实现您的目标：生成一个 GUID 并为自己编写一个函数，该函数根据 GUID 计算您的数字。 man uuid 如果您使用的是 unix 系统。否则 google 它。 uuid 的某些部分不是随机的但包含元信息，某些部分是系统的（例如您的网卡 MAC 地址）或随机的，具体取决于生成器算法。但它们非常非常有可能是独一无二的。因此，每当您需要一个新的唯一编号时，请生成一个 uuid 并通过某种算法将其转换为您的编号，该算法基本上以非平凡的方式将 uuid 字节映射到您的编号（例如使用哈希函数）。
感谢您提出有趣的问题。您可以使用模幂创建具有几个字节的 "pseudorandom"*（循环）排列。假设我们有 n 个元素。搜索大于 n+1 的素数 p。然后找到原根 g 模 p。基本上根据原根的定义，动作 x --> (g * x) % p 是 {1, ..., p-1} 的循环排列。所以 x --> ((g * (x+1))%p) - 1 是 {0, ..., p-2} 的循环排列。如果它给出的值大于（或等于）n，我们可以通过重复先前的排列来获得 {0, ..., n-1} 的循环排列。
我将这个想法实现为一个 Go 包。 https://github.com/bwesterb/powercycle
package main
import (
"fmt"
"github.com/bwesterb/powercycle"
)
func main() {
var x uint64
cycle := powercycle.New(10)
for i := 0; i < 10; i++ {
fmt.Println(x)
x = cycle.Apply(x)
}
}
这输出类似
0
6
4
1
2
9
3
5
8
7
但这可能会有所不同，具体取决于所选的发电机。
它很快，但不是超快：在我 5 岁的 i7 上，计算 1000000000000000 个元素上的一个循环应用程序需要不到 210ns。更多详情：
BenchmarkNew10-8 1000000 1328 ns/op
BenchmarkNew1000-8 500000 2566 ns/op
BenchmarkNew1000000-8 50000 25893 ns/op
BenchmarkNew1000000000-8 200000 7589 ns/op
BenchmarkNew1000000000000-8 2000 648785 ns/op
BenchmarkApply10-8 10000000 170 ns/op
BenchmarkApply1000-8 10000000 173 ns/op
BenchmarkApply1000000-8 10000000 172 ns/op
BenchmarkApply1000000000-8 10000000 169 ns/op
BenchmarkApply1000000000000-8 10000000 201 ns/op
BenchmarkApply1000000000000000-8 10000000 204 ns/op
为什么我说"pseudorandom"？好吧，我们总是在创建一种非常特殊的循环：即使用模幂的循环。不过它看起来很伪随机。