少年，洗个牌吧 #14
Labels
Comments
function random(num) {
let arr = new Array(num)
for (let i = 0; i < num; i++) {
arr[i] = i
}
for (let i = 0; i < num; i++) {
let x = Math.floor(Math.random() * num)
, tmp = arr[x]
arr[x] = arr[i]
arr[i] = tmp
}
return arr
}这个怎么样0.0 |
|
@koi646 这个不算是很随机吧 等价于 从 n 个数里面选数，选出一个之后不是从剩下的 n-1 里面选择，而是继续从 n 个数里面选择 关于上面我写的那种的随机证明，可以参加《算法导论》的证明 😂 |
|
这个也是完全随机的。 undersorce源码里面随机打乱就是这样写的... |
|
@koi646 抱歉，我概率论学的不是很好，但冥冥之中感觉你的做法还是存在问题的。 我试着测了一下数据： 5 个数组的全排列 代码： 'use strict'
function method1() {
let A = []
function rd(n,m){
return Math.floor(Math.random() * (m-n+1) + n);
}
for(let i = 0; i < 5; i++) {
A[i] = i + 1;
}
for(let i = 0; i < 5 - 1; i++) {
let index = rd(i+1, 5-1);
A[i] = A[i] ^ A[index]
A[index] = A[index] ^ A[i]
A[i] = A[i] ^ A[index]
}
return A.join("、")
}
function method2(num) {
let arr = new Array(num)
for (let i = 0; i < num; i++) {
arr[i] = i
}
for (let i = 0; i < num; i++) {
let x = Math.floor(Math.random() * num)
, tmp = arr[x]
arr[x] = arr[i]
arr[i] = tmp
}
return arr.join("、")
}
let result1 = {}
for(let i = 0; i < 10000; i++) {
let key = method1()
if(key in result1) {
result1[key] ++
} else {
result1[key] = 1
}
}
console.log(JSON.stringify(result1, null, 3))
console.log("==============")
let result2 = {}
for(let i = 0; i < 10000; i++) {
let key = method2(4)
if(key in result2) {
result2[key] ++
} else {
result2[key] = 1
}
}
console.log(JSON.stringify(result2, null, 3))得到的结果如下： 比较多的测试了好几次，结果都是类似。 即按你所说的方式随机性并不是特别好。（如果我的代码不存在问题的话） 我认为对于一般的随机你的做法完全是可以的，但是如果说是让概率更加的平均，我还是认为《算法导论》中的做法比较好。 具体证明要请数学大神了....... |
|
我也试了一下 好像是这样..那个方法貌似正确但是不严谨... |
|
@koi646 一般情况下肯定是够用的 😂 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
问题
如何利用已知random()函数，求一个1~N的全排列？
详细描述
已知：一个random()函数可以生成一个(0,1)范围内的浮点数。
要求：输入N，利用random()函数，生成一个1至N的全排列。
例如：当输入N = 4,生成结果可以为1324或3214等等，并保证等概率。
正文
Step 1
这个题最自然的想法莫过于连续产生随机数，然后如果产生的这个随机数之前没有产生过，就记录并且输出。
这样做显然是能得到结果的，并且能保证足够的随机。
但存在的问题就是会产生些许的浪费，每次产生随机数之后都要确认曾经是否产生过。尤其是对于这样的场景，比如 1 - 3 的全排列，如果已经产生了 3、2，那么我们一定能够确定的是这个全排列的最后一个数一定是 1 ，同样对于倒数第二个数也存在这样的浪费。
Step 2
换种想法，我们可以先做个循环或者其他的方法，产生这么多的数，然后如果能把这些数的顺序随机打乱，也就是一种很好的解法了。
那么问题是如何去随机的打算他们，保证概率呢？
《算法导论》这本书上给过相关的方法，并且有充分的证明。怎么做呢？
伪代码如下：
RANDOMIZE_IN_PLACE (A)
那简单的来看如何去理解呢？我们都知道抓阄这个方法是公平的，所以同理，这个方法可以这样理解，有 n 个阄，从 n 个里抓一个，然后剩余 n - 1 个，然后继续从剩下的 n - 1 里面抓。这样保证每个阄都是公平出现的。
这段代码用 JavaScript 实现如下：
Step 3
这也就是著名的洗牌算法
版权声明
捐赠
写文不易，赠我一杯咖啡增强一下感情可好？
The text was updated successfully, but these errors were encountered: