少年，洗个牌吧

[rccoder]

问题

如何利用已知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 = A.length
for i=1 to n
  swap A[i] with A[Random(i, n)]

那简单的来看如何去理解呢？我们都知道抓阄这个方法是公平的，所以同理，这个方法可以这样理解，有 n 个阄，从 n 个里抓一个，然后剩余 n - 1 个，然后继续从剩下的 n - 1 里面抓。这样保证每个阄都是公平出现的。

这段代码用 JavaScript 实现如下：

A = []

function rd(n,m){  
  return Math.floor(Math.random() * (m-n+1) + n);
}

for(let i = 0; i < 100; i++) {
  A[i] = i + 1;
}

for(let i = 0; i < 100 - 1; i++) {
  let index = rd(i+1, 100-1);

  A[i] = A[i] ^ A[index]
  A[index] = A[index] ^ A[i]
  A[i] = A[i] ^ A[index]
}

console.log(A.join("、"))

Step 3

这也就是著名的洗牌算法

---

版权声明

• 请尊重辛勤劳动
• 禁止不署名完全转载，可单独通过下面的捐赠付版权费
• 建议署名并进行摘要性质转载

  捐赠

写文不易，赠我一杯咖啡增强一下感情可好？

[koi646]

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

[rccoder]

@koi646 这个不算是很随机吧

等价于

从 n 个数里面选数，选出一个之后不是从剩下的 n-1 里面选择，而是继续从 n 个数里面选择

---

关于上面我写的那种的随机证明，可以参加《算法导论》的证明 😂

[koi646]

这个也是完全随机的。 每个数出现在各个位置的概率是相等的,就是完全随机。 遍历数组 第一步交换 0出现在任意位置的概率相等, 第二步交换1 出现在任意位置的概率相等 ....

undersorce源码里面随机打乱就是这样写的...

[rccoder]

@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))

得到的结果如下：

{
   "3、1、5、2、4": 384,
   "3、4、2、5、1": 423,
   "4、3、1、5、2": 461,
   "5、1、4、2、3": 422,
   "5、1、2、3、4": 442,
   "4、3、5、2、1": 419,
   "3、5、4、2、1": 393,
   "5、3、1、2、4": 422,
   "2、5、1、3、4": 405,
   "5、4、2、1、3": 404,
   "2、3、5、1、4": 412,
   "3、4、5、1、2": 413,
   "3、1、4、5、2": 426,
   "5、3、4、1、2": 405,
   "3、5、2、1、4": 442,
   "4、1、2、5、3": 414,
   "2、4、5、3、1": 381,
   "2、4、1、5、3": 442,
   "5、4、1、3、2": 409,
   "2、3、4、5、1": 417,
   "4、5、1、2、3": 404,
   "4、5、2、3、1": 433,
   "4、1、5、3、2": 446,
   "2、5、4、1、3": 381
}
==============
{
   "0、1、3、2": 381,
   "2、0、3、1": 436,
   "0、3、2、1": 369,
   "2、0、1、3": 452,
   "3、1、2、0": 287,
   "0、2、3、1": 561,
   "0、3、1、2": 412,
   "1、2、0、3": 543,
   "1、3、0、2": 412,
   "2、3、0、1": 419,
   "3、1、0、2": 381,
   "0、1、2、3": 364,
   "1、3、2、0": 432,
   "3、2、1、0": 370,
   "3、0、1、2": 322,
   "1、2、3、0": 584,
   "3、2、0、1": 380,
   "2、1、0、3": 336,
   "1、0、2、3": 400,
   "0、2、1、3": 414,
   "2、1、3、0": 433,
   "1、0、3、2": 589,
   "3、0、2、1": 346,
   "2、3、1、0": 377
}

比较多的测试了好几次，结果都是类似。

即按你所说的方式随机性并不是特别好。（如果我的代码不存在问题的话）

---

我认为对于一般的随机你的做法完全是可以的，但是如果说是让概率更加的平均，我还是认为《算法导论》中的做法比较好。

具体证明要请数学大神了.......

[koi646]

我也试了一下 好像是这样..那个方法貌似正确但是不严谨... 学到了~0.0

[rccoder]

@koi646 一般情况下肯定是够用的 😂