# 毎日一题 -  洗牌算法

## 信息卡片

* 时间：2019-07-19
* 题目链接：暂无
* tag：`Array` `Probability`

## 题目描述

```
假设我们有一个n个元素的数组，要求你实现一个函数，该函数会随机地返回n个元素的排列，要求所有排列出现的概率是一样的。即每一个排列出现的概率都是1/n!.
```
## 参考答案
思路如下

像洗牌一样，从数组中随机取出一个，放入另一个全新的数组中，但这会涉及到数组删除操作.
在这个基础上转换一下思路把从数组中取出的元素放入原数组中，第一次随机删除时，把它与原数组的倒数第一个交换，第2次在剩下的元素中随机删除时，把它与原数组的倒数第2个交换，第n-1次（最后一次不用换）时便完成了洗牌 时间复杂度为O(n)

```js
	function shuffle(list) {
	  for (let i = list.length - 1; i >= 1; i--) {
	    const random = (Math.random() * (i + 1)) >> 0;
	    const temp = list[i];
	    list[i] = list[random];
	    list[random] = temp;
	  }
	}
```
注： 概率证明， 任意一个元素放在倒数第一个位置的概率为1/n,放到倒数第2个的概率为  [(n-1)/n ]* [1/(n-1)] = 1/n,放在倒数第k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] *...* [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n， 因此每一个元素放在任意位置的概率都为1/n,所有的排列出现的概率则为 1/n * 1/(n-1) *..* 1 = 1/n!

注：在交换时，之所以第一次与第n个交换不与第一个交换，是因为与第n个交换代码更简洁

## 优秀解答

>暂缺