shell实现Fisher–Yates shuffle洗牌算法介绍

目录
  • Fisher-Yates shuffle 算法简介
  • shell实现

本文介绍使用shell语法实现Fisher–Yates shuffle 洗牌算法。

Fisher-Yates shuffle 算法简介

Fisher–Yates shuffle 洗牌算法可以用于对数组进行随机排列，它的时间复杂度为O(n)，伪代码如下：

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 <= j <= i
	exchange a[j] and a[i]

假定有一个数组a=[1, 2, 3, 4, 5, 6, 7, 8, 9]，数组长度为n，打乱a中元素的具体迭代步骤如下：

生成一个[0, n-1]区间的随机数k；将第k个元素和第n-1个元素进行交换；进行下一轮迭代，生成一个[0, n-2]区间的随机数k，将第k个元素和第n-2个元素进行交换， 迭代次数为n-1次：从n-1取到1；最终得到一个打乱的数组。

下表是一个数组的具体打乱过程，打乱后的数组是(9 4 8 1 2 3 5 6 7)

随机数 原数组 新数组
0-8：6 a = (1 2 3 4 5 6 7 8 9) 交换a[8]和a[6] ：(1 2 3 4 5 6 9 8 7)
0-7：5 a = (1 2 3 4 5 6 9 8 7) 交换a[7]和a[5] ：(1 2 3 4 5 8 9 6 7)
0-6：4 a = (1 2 3 4 5 8 9 6 7) 交换a[6]和a[4] ：(1 2 3 4 9 8 5 6 7)
0-5：2 a = (1 2 3 4 9 8 5 6 7) 交换a[5]和a[2] ：(1 2 8 4 9 3 5 6 7)
0-4：1 a = (1 2 8 4 9 3 5 6 7) 交换a[4]和a[1] ：(1 9 8 4 2 3 5 6 7)
0-3：0 a = (1 9 8 4 2 3 5 6 7) 交换a[3]和a[0] ：(4 9 8 1 2 3 5 6 7)
0-2：2 a = (4 9 8 1 2 3 5 6 7) 交换a[2]和a[2] ：(4 9 8 1 2 3 5 6 7)
0-1：0 a = (4 9 8 1 2 3 5 6 7) 交换a[1]和a[0] ：(9 4 8 1 2 3 5 6 7)

shell实现

shuffle.sh :

#!/bin/bash

shuffle() {
   local i tmp size max rand
   # 打乱顺序
   # Knuth-Fisher-Yates shuffle algorithm
   size=${#my_array[*]}
   max=$(( 32767 / size * size ))
   # echo "max: $max"
   for ((i=size-1; i>0; i--)); do
      while (( (rand=$RANDOM) >= max )); do :; done
      rand=$(( rand % (i+1) ))
      # 交换
      tmp=${my_array[i]}
      my_array[i]=${my_array[rand]}
      my_array[rand]=$tmp
      echo ${my_array[*]}
   done
}

my_array=(1 2 3 4 5 6 7 8 9)
shuffle
echo ${my_array[*]}

执行效果：

$ sh shuffle.sh
1 2 3 4 9 6 7 8 5
1 8 3 4 9 6 7 2 5
7 8 3 4 9 6 1 2 5
7 8 6 4 9 3 1 2 5
7 8 6 9 4 3 1 2 5
7 9 6 8 4 3 1 2 5
7 6 9 8 4 3 1 2 5
7 6 9 8 4 3 1 2 5

到此这篇关于shell实现Fisher–Yates shuffle洗牌算法介绍的文章就介绍到这了,更多相关shell Fisher–Yates shuffle洗牌算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • shell 中小括号、中括号及大括号的区别解析

    目录 一.小括号,圆括号() 1.单小括号 () 2.双小括号 (( )) 二.中括号,方括号[] 1.单中括号 [] 2.双中括号[[ ]] 三.大括号.花括号 {} 1.常规用法 2.几种特殊的替换结构 一.小括号,圆括号() 1.单小括号 () ①命令组.括号中的命令将会新开一个子shell顺序执行,所以括号中的变量不能够被脚本余下的部分使用.括号中多个命令之间用分号隔开,最后一个命令可以没有分号,各命令和括号之间不必有空格. ②命令替换.等同于`cmd`,shell扫描一遍命令行,发现了

  • shell脚本for循环实现文件和目录遍历

    shell脚本for循环实现文件和目录遍历

    一个for循环实现一个目录下的文件和目录遍历,很实用 [root@localhost shell_order]# cat test27.sh #!/bin/bash #print the directory and file for file in /home/hustyangju/* do if [ -d "$file" ] then echo "$file is directory" elif [ -f "$file" ] then echo

  • Shell编程条件测试的实现

    目录 什么是Shell 编写Shell脚本 条件测试 | 数值测试 条件测试 | 字符串测试 条件测试 | 文件状态测试 条件测试的逻辑操作符 什么是Shell Shell是一个命令解释器,它会解释并执行命令行提示符下输入的命令.除此之外,Shell还有另一个功能,如果要执行多条命令,它可以将这组命令存放在一个文件中,然后可以像执行Linux系统提供的其他程序一样执行这个文件,这个命令文件就叫做Shell程序或者Shell脚本.当运行这个文件时,它会像在命令行输入这些命令一样顺序地执行它们. S

  • shell实现Fisher–Yates shuffle洗牌算法介绍

    目录 Fisher-Yates shuffle 算法简介 shell实现 本文介绍使用shell语法实现Fisher–Yates shuffle 洗牌算法. Fisher-Yates shuffle 算法简介 Fisher–Yates shuffle 洗牌算法可以用于对数组进行随机排列,它的时间复杂度为O(n),伪代码如下: To shuffle an array a of n elements (indices 0..n-1): for i from n - 1 downto 1 do j =

  • JS随机洗牌算法之数组随机排序

    JS随机洗牌算法之数组随机排序

    推荐阅读:JavaScript学习笔记之数组的增.删.改.查 JavaScript学习笔记之数组求和方法 JavaScript学习笔记之数组随机排序 洗牌算法是一个比较形象的术语,本质上让一个数组内的元素随机排列.举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9: 从上面这个数组入手,我们要做的就是打乱数组内元素的顺序: 代码实现 维基百科上的 Fisher–Yates shuffle 词条对洗牌算法做了详细介绍,下面演示的算法也是基于其中的理论编写的: A

  • php实现简单洗牌算法

    如下所示: 复制代码 代码如下: <?php  /**   * 简单洗牌算法   */ $card_num=54; //牌数  print_r(wash_card($card_num)); function wash_card($card_num)  {      $cards=$tmp=array();      for($i=0;$i<$card_num;$i++){          $tmp[$i]=$i;      } for($i=0;$i<$card_num;$i++){

  • javascript随机之洗牌算法深入分析

    洗牌算法是我们常见的随机问题,在玩游戏.随机排序时经常会碰到.它可以抽象成这样:得到一个M以内的所有自然数的随机顺序数组. 在百度搜"洗牌算法",第一个结果是<百度文库-洗牌算法>,扫了一下里面的内容,很多内容都容易误导别人走上歧途,包括最后用链表代替数组,也只是一个有限的优化(链表也引入了读取效率的损失). 该文里的第一种方法,可以简单描述成:随机抽牌,放在另一组:再次抽取,抽到空牌则重复抽."抽到空牌则重复抽"这会导致后面抽到空牌的机会越来越大,显然

  • C#实现洗牌算法

    C#洗牌算法,简单演示! /// <summary> /// 洗牌算法 /// </summary> private void test() { int[] iCards = new int[54]; for (int i = 0; i < iCards.Length; i++) { iCards[i] = i + 1; } // Random rand = new Random(); int iTarget = 0, iCardTemp = 0; for (int i =

  • JavaScript随机打乱数组顺序之随机洗牌算法

    假如有一个数组是这样子: var arr1 = ["a", "b", "c", "d"]; 如何随机打乱数组顺序,也即洗牌. 有一个比较广为传播的简单随机算法: function RandomSort (a,b){ return (0.5 - Math.random()); } 实际证明上面这个并不完全随机. 随便一搜网上太多这种东西了,看一下stackoverflow上的一个高分回答,答案出自github上. knuth-s

  • Shell脚本实现乱序排列文件内容的多种方法（洗牌问题）

    洗牌问题:洗一副扑克,有什么好办法?既能洗得均匀,又能洗得快?即相对于一个文件来说怎样高效率的实现乱序排列? ChinaUnix 确实是 Shell 高手云集的地方,只要你想得到的问题,到那里基本上都能找到答案.r2007给出了一个取巧的方法,利用 Shell 的 $RANDOM 变量给原文件的每一行加上随机的行号然后根据这个随机行号进行排序,再把临时加上去的行号给过滤掉,这样操作之后得到的新文件就相当于被随机"洗"了一次: 复制代码 代码如下: while read i;do ech

  • JavaScript实现shuffle数组洗牌操作示例

    JavaScript实现shuffle数组洗牌操作示例

    本文实例讲述了JavaScript实现shuffle数组洗牌操作.分享给大家供大家参考,具体如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"&g

  • 在Python中实现shuffle给列表洗牌

    如下所示: # Copyright (c)2018, 东北大学软件学院学生 # All rightsreserved # 文件名称:a.py # 作 者:孔云 #问题描述:shuffle函数可以给列表洗牌 import random dessert=['ice cream','pancake','brownies','cookies','candy'] random.shuffle(dessert) print(dessert) 运行结果如下: 注:列表打印出来是洗牌后的结果,顺序完全不一样.如

  • C#实现洗牌游戏实例

    C#实现洗牌游戏实例

    棋牌类游戏是目前比较火的游戏之一.今天本文就以实例形式实现洗牌游戏.本文实例所采用的算法是:遍历每个位置上的牌,然后与随机位置上的牌交换. 运行结果如下图所示: 对于牌来讲,2个关键的因素是面值和类型(如红桃.梅花等). 代码如下: public class Card { private string mianzhi; private string leixin; public Card(string m, string l) { mianzhi = m; leixin = l; } publi

随机推荐