重置数组

[serendipityApe]

题目

重置一个数组,（洗牌） 原题目: can you shuffle() an array?

例子

如let arr = [1,2,3,4] 可能有4 3 2 * 1 24种排列。 [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] [1, 4, 3, 2] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 1, 3] [2, 4, 3, 1] [3, 1, 2, 4] [3, 1, 4, 2] [3, 2, 1, 4] [3, 2, 4, 1] [3, 4, 1, 2] [3, 4, 2, 1] [4, 1, 2, 3] [4, 1, 3, 2] [4, 2, 1, 3] [4, 2, 3, 1] [4, 3, 1, 2] [4, 3, 2, 1]

shuffle方法应该以相同的概率(1/24)讲arr转换成上述任意一个数组。

答案

// 数组第一个元素被置换的几率为1/n;
// 第二个元素被置换的几率为  n-1/n * 1/n-1 = 1/n
// 以此类推,每个元素被置换的几率都为 1/n
function shuffle(arr){
 for(let i=0;i<arr.length-1;i++){
  let j = i + parseInt(Math.random() *(arr.length - i));
  [ arr[i] , arr[j] ] = [ arr[j] , arr[i] ];
 }
}