洗牌算法

omgdog 發布于2019-08-23 17:53 / 2636人閱讀

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

洗牌算法 Fisher-Yates Shuffle

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

描述：

寫下從 1 到 N 的數字

取一個從 1 到剩下的數字（包括這個數字）的隨機數 k

從低位開始，得到第 k 個還沒有被取出的數字，把它寫在獨立的一個列表的最后一位

重復第 2 步，直到所有的數字都被取出

第 3 步寫出的這個序列，現在就是原始數字的隨機排列

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 等人的基礎上對算法進行了改進，不借助新的組數，直接在原地交換。該算法的基本思想和 Fisher 類似，每次從未處理的數據中隨機取出一個數，并和最后一個剩余元素交換，然后剩余元素的數量減一。

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 算法的思想是從前往后，借助舊數組，將新數組中位置 k 和位置 i 的數字進行交互。

描述

拷貝數組

從 i(0 - N)掃描數組，選擇一個隨機數 k( 0 <= k <= i)

新數組的[i] = 新數組的[k], 新數組的[k] = 原始數組[i]

重復第 2 步，直到末尾

最終的新數組就是隨機的

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

云服務器 GPU云服務器 python洗牌算法隨機洗牌 python洗牌國際cdn洗牌

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/104294.html

隨機問題之洗牌算法

摘要：百度文庫洗牌算法提到一種換牌思路隨機交換兩個位置，共交換次，越大，越接近隨機。洗牌插牌法優化版，可以用數學歸納法證明，這種洗牌是均勻的。每次生成一張最大的牌，與隨機的某張牌換位子抽牌抽牌優化換牌插牌插牌優化文章轉載自隨機問題之洗牌算法洗牌算法是我們常見的隨機問題，在玩游戲、隨機排序時經常會碰到。它可以抽象成這樣一個問題。得到一個M以內的所有自然數的隨機順序數組。在百度搜洗牌算法，...

instein 2019-08-19 17:13 評論0 收藏0
數組隨機排序：洗牌算法(Fisher–Yates shuffle)

摘要：代碼實現代碼一測試用例輸出其中，代碼二測試用例輸出其中，參考資料洗牌算法學習筆記數組隨機排序洗牌算法給數組隨機排序洗牌算法原理原理及步驟 1.定義一個數組（shuffled），長度（length）是原數組（arr）長度2.取 0 到 index (初始0) 隨機值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...

張金寶 2019-08-20 15:27 評論0 收藏0
程序員的算法趣題Q50: 完美洗牌

摘要：的結果與原書的結果不符。上一篇程序員的算法趣題欲速則不達程序員的算法趣題欲速則不達下一篇程序員的算法趣題同時結束的沙漏本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解目錄 1. 問題描述 ?2. 解題分析 2.1 思路1 2.2 思路2 3. 代碼及測試 4....

xeblog 2021-10-11 10:58 評論0 收藏0
Underscore 源碼（三）隨機洗牌算法

摘要：隨機洗牌算法說實話，以前理解數組的排序，都是將數組按照一定的邏輯由大到小或者由小到大排序，我自己是沒有碰到過隨機打亂數組排序的問題。然后里用的是所謂的洗牌算法，很高效。總結又是三個知識點，分別是隨機洗牌分組和函數的實現，沒什么復雜的。這是第三篇關于 Underscore 的源碼解讀，最近一段時間學的東西很少，自己太忙了，一方面忙著找實習，晚上回去還要寫畢業論文。畢業論文真的很憂傷，因...

silencezwm 2019-08-20 16:42 評論0 收藏0
js 數組隨機數數組洗牌

摘要：首先通過數組調用是令系統隨機選取大于等于且小于的偽隨機值進入到函數后分別定義了變量和變量為當前數組的長度，先聲明，以便在下面中使用。循環一圈后就形成了對數組的洗牌。這次分享一個隨機數組洗牌的一個算法，讓你得到隨機數組。假如1個數組的值是這樣的： const arr = [a, b, c, d, e, f, g]; 因為在實踐操作中，在網上搜可以搜到一大堆隨機的這些代碼。但是實際上究...

jay_tian 2019-08-26 10:30 評論0 收藏0