`

Fisher–Yates shuffle - Shuffle an Array in Place

阅读更多

Question: How do you shuffle an array in place?

伪代码如下:

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ ji
       exchange a[j] and a[i]
// Shuffle a deck of cards
Random random = new Random();
for (int i = cards.size() - 1; i >= 0; i--) {
    int j = random.nextInt(i + 1);
    /* swap cards i,j */
    Card card = cards.get(i);
    cards.set(i, cards.get(j));
    cards.set(j, card);
}

The Fisher–Yates shuffle, as implemented by Durstenfeld, is an in-place shuffle. That is, given a preinitialized array, it shuffles the elements of the array in place, rather than producing a shuffled copy of the array. This can be an advantage if the array to be shuffled is large.

To simultaneously initialize and shuffle an array, a bit more efficiency can be attained by doing an "inside-out" version of the shuffle. In this version, one successively places element number i into a random position among the first i positions in the array, after moving the element previously occupying that position to position i. In case the random position happens to be number i, this "move" (to the same place) involves an uninitialised value, but that does not matter, as the value is then immediately overwritten. No separate initialization is needed, and no exchange is performed. In the common case where source is defined by some simple function, such as the integers from 0 to n − 1, source can simply be replaced with the function sincesource is never altered during execution.

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
  for i from 0 to n − 1 do
      j ← random integer with 0 ≤ ji
      if ji
          a[i] ← a[j

a[j] ← source[i

We'll start by writing out the numbers from 1 to 8 as before:

Range Roll Scratch Result
    1 2 3 4 5 6 7 8  

For our first roll, we roll a random number from 1 to 8: this time it's 6, so we swap the 6th and 8th numbers in the list:

Range Roll Scratch Result
1–8 6 1 2 3 4 5 8 7 6

The next random number we roll from 1 to 7, and turns out to be 2. Thus, we swap the 2nd and 7th numbers and move on:

Range Roll Scratch Result
1–7 2 7 3 4 5 8 2 6

The next random number we roll is from 1 to 6, and just happens to be 6, which means we leave the 6th number in the list (which, after the swap above, is now number 8) in place and just move to the next step. Again, we proceed the same way until the permutation is complete:

Range Roll Scratch Result
1–6 6 1 7 3 4 5 8 2 6
1–5 1 5 7 3 4 1 8 2 6
1–4 3 5 7 4 3 1 8 2 6
1–3 3 5 7 4 3 1 8 2 6
1–2 1 7 5 4 3 1 8 2 6

At this point there's nothing more that can be done, so the resulting permutation is 7 5 4 3 1 8 2 6.

 

分享到:
评论

相关推荐

    洗牌算法(Fisher–Yates Shuffle and Knuth-Durstenfeld Shuffle)

    Fisher–Yates Shuffle and Knuth-Durstenfeld Shuffle洗牌算法的C++实现。

    Fisher-Yates-Shuffle:随机数。 编程问题

    费雪-耶茨洗牌算法(Fisher-Yates Shuffle),也称为Knuth洗牌,是计算机科学中一种常用的算法,用于生成一个数组的随机排列。这个算法由伊万·费雪和伦纳德·耶茨在1948年提出,后来在唐·克努斯的《计算机程序设计...

    js代码-数组乱序,实现一个数组乱序,每一个元素出现在每一个位置的概率是平均的 Fisher–Yates shuffle费雪耶兹随机置乱算法

    本文将深入探讨如何使用Fisher–Yates (也称为Knuth) shuffle算法来实现一个数组的均匀乱序,确保每个元素出现在每个位置的概率是相等的。 Fisher–Yates shuffle算法是一个经典的随机化算法,它通过对数组进行原地...

    fast-shuffle:Fisher-Yates Shuffle的快速,纯净,无副作用和确定性实现

    用法npm install --save fast-shuffleimport { shuffle } from 'fast-shuffle'const suits = [ ':club_suit:' , ':diamond_suit:' , ':heart_suit:' , ':spade_suit:' ]const faces = [ '2' , '3' , '4' , '5' , '6'...

    shuffle:Fisher-Yates shuffle洗牌算法

    Fisher-Yates shuffle洗牌算法 执行node shuffle.js运行 生成100000个数组[0,1,2,3,4,5,6,7,8,9],使用洗牌算法洗牌,计算每个数出现的各个位置的概率 [ '9.93% | 10.10% | 9.94% | 9.91% | 9.93% | 9.89% | 10.10% ...

    shuffle-and-sort

    **打乱(Shuffle)** 过程通常使用**Fisher-Yates(也称为Knuth)洗牌算法**。这是一种保证均匀分布的随机洗牌算法,适用于数组。基本步骤包括从最后一个元素开始,对每个元素与其后面未洗牌的元素进行随机交换,...

    前端项目-knuth-shuffle.zip

    《前端项目:Fisher-Yates(Knuth)洗牌算法在浏览器与Node.js中的实现》 在前端开发中,我们经常遇到需要随机排列数组元素的需求,例如在制作卡牌游戏或者随机显示列表时。Fisher-Yates(也称为Knuth)洗牌算法是...

    fisher-yates:一个紧凑的模块,可以对数组进行随机排序

    渔民 一个紧凑的模块,用于对数组进行随机排序。... var shuffleInplace = require ( 'fisher-yates/inplace' ) var array = [ 1 , 2 , 3 ] shuffleInplace ( array ) console . log ( array ) // => [2, 1, 3]

    shuffle-stream:随机播放流

    使用就地 Fisher-Yates 算法提高速度。用法 var shuffle = require ( 'shuffle-stream' ) , opts = { // Optional, default false. Set to true if not // pushing buffers or strings. objectMode : false // ...

    flipcard:Flippin的记忆卡游戏

    翻盖翻页卡 Flippin的记忆卡游戏 入门 翻转纸牌进行游戏,匹配两张,直到您匹配所有纸牌!... (音频) (某些CSS按钮会影响)Fisher-Yates Shuffle-博斯特。 ocks.org/mike/shuffle(shuffle algorithim)

    Java中 shuffle 算法的使用

    这个概念源于Fisher–Yates shuffle算法,也被称为Knuth shuffle。它是一种在原地进行的洗牌算法,即不需要额外的存储空间。这个算法的主要目的是确保经过洗牌后,数组的每个元素都有相等的概率出现在任何位置上。 ...

    python 实现 leetcode 各种问题 课程设计 代码

    Fisher-Yates洗牌算法(Fisher-Yates Shuffle) 高斯复活节计算(Gauss Easter) 格雷厄姆扫描算法(Graham Scan) 贪婪算法(Greedy) 猜数字搜索(Guess The Number Search) H指数(H Index) 最近最少使用...

    Fisher代码实现.zip

    Fisher编码,全称为Fisher-Yates编码,也被称为Knuth shuffle,是一种在计算机科学中用于随机排列数组元素的算法。这个算法由Fisher和Yates提出,后来被Donald Knuth在他的著作《The Art of Computer Programming》...

    洗牌算法整理

    - **Fisher-Yates shuffle**(高纳德算法):每次随机选择一个元素与数组末尾元素交换,缩小处理范围,直到只剩一个元素。这种方法在原地修改数组,时间复杂度为O(N),空间复杂度为O(1)。 - **Inside-Out ...

    weighted_shuffle

    加权洗牌 Fisher-Yates-Shuffle算法的扩展以支持权重。 它包括Ruby核心扩展阵列的便利性。安装将此行添加到应用程序的Gemfile中: gem 'weighted_shuffle'然后执行: $ bundle或将其自己安装为: $ gem install ...

    Randomizes an array of any size (integer or string).

    在实际应用中,可能会根据需求添加更多的功能,例如,验证随机化是否成功(即数组元素的顺序确实发生了变化),或者支持特定的随机化算法(如Fisher-Yates shuffle)。此外,对于大型数组,优化算法的效率也非常重要...

    shuffle-music-player:一个基于Node.js的示例音乐播放器,可在随机播放时流式播放曲目

    "shuffle-music-player" 是一个基于 Node.js 开发的音乐播放器项目,它的核心功能是实现音乐的随机播放,并且能够支持流式播放。这意味着它能够在不完全加载整个音乐文件的情况下,逐段播放音乐,提高了用户体验,...

    随机排行实现

    有多种方法可以实现随机排序,其中一种简单的方法是"鱼洗排序"(Fisher-Yates shuffle),也称为Knuth shuffle。这种算法直接在原数组上进行操作,通过将每个元素与数组中随机位置的元素交换来达到随机排列的目的。...

    fisher-shuffle:一组实用程序函数可根据** Fisher-Yates算法**随机播放并生成随机数组序列。 该程序包使用打字稿编写,并且不依赖于任何其他程序包。 该软件包作为npm模块发布

    Fisher shuffle的工作原理是在每次迭代时生成随机索引i和j ,然后将array[i]和array[j]交换以使数组随机化,像shuffleArrayInPlace和shuffleArray这样的函数都是基于此原理设计的,但并非所有用例都可以需要改组...

Global site tag (gtag.js) - Google Analytics