洗牌算法

omgdog 發(fā)布于2019-08-23 17:53 / 2644人閱讀

摘要：描述拷貝數(shù)組從掃描數(shù)組，選擇一個(gè)隨機(jī)數(shù)新數(shù)組的新數(shù)組的新數(shù)組的原始數(shù)組重復(fù)第步，直到末尾最終的新數(shù)組就是隨機(jī)的參考三種洗牌算法

洗牌算法 Fisher-Yates Shuffle

Fisher–Yates 隨機(jī)置亂算法，通俗說就是生成一個(gè)有限集合的隨機(jī)排列。

描述：

寫下從 1 到 N 的數(shù)字

取一個(gè)從 1 到剩下的數(shù)字（包括這個(gè)數(shù)字）的隨機(jī)數(shù) k

從低位開始，得到第 k 個(gè)還沒有被取出的數(shù)字，把它寫在獨(dú)立的一個(gè)列表的最后一位

重復(fù)第 2 步，直到所有的數(shù)字都被取出

第 3 步寫出的這個(gè)序列，現(xiàn)在就是原始數(shù)字的隨機(jī)排列

function getRandom(arr, length) {
  const random = Math.floor(Math.random() * length)

  // 原始算法將在此處消耗較多資源
  if (arr.includes(random)) {
    return getRandom(arr, length)
  } else {
    return random
  }
}

function randomArray(arr) {
  let newArr = []
  const length = arr.length
  let index = length - 1
  let indexArr = []
  while (index >= 0) {
    const random = getRandom(indexArr, length)
    indexArr.push(random)
    newArr.push(arr[random])
    --index
  }

  return newArr
}

Knuth-Durstenfeld Shuffle

Knuth 和 ?Durstenfeld ? 在 Fisher 等人的基礎(chǔ)上對(duì)算法進(jìn)行了改進(jìn)，不借助新的組數(shù)，直接在原地交換。該算法的基本思想和 Fisher 類似，每次從未處理的數(shù)據(jù)中隨機(jī)取出一個(gè)數(shù)，并和最后一個(gè)剩余元素交換，然后剩余元素的數(shù)量減一。

function randomArray(arr) {
  const length = arr.length
  for (let index = length - 1; index > 0; index--) {
    const random = Math.floor(Math.random() * index)
    const temp = arr[index]
    arr[index] = arr[random]
    arr[random] = temp
  }

  return arr
}

Inside-Out Algorithm

Inside-Out Algorithm 算法的思想是從前往后，借助舊數(shù)組，將新數(shù)組中位置 k 和位置 i 的數(shù)字進(jìn)行交互。

描述

拷貝數(shù)組

從 i(0 - N)掃描數(shù)組，選擇一個(gè)隨機(jī)數(shù) k( 0 <= k <= i)

新數(shù)組的[i] = 新數(shù)組的[k], 新數(shù)組的[k] = 原始數(shù)組[i]

重復(fù)第 2 步，直到末尾

最終的新數(shù)組就是隨機(jī)的

function randomArray(arr) {
  let newArr = arr.concat([])
  const length = arr.length
  for (let index = 0; index < length; index++) {
    const random = Math.floor(Math.random() * (index + 1))
    newArr[index] = newArr[random]
    newArr[random] = arr[index]
  }

  return newArr
}

參考

三種洗牌算法 shuffle

Fisher–Yates shuffle From Wikipedia