shell實(shí)現(xiàn)Fisher–Yates shuffle洗牌算法介紹
本文介紹使用shell語法實(shí)現(xiàn)Fisher–Yates shuffle 洗牌算法。
Fisher-Yates shuffle 算法簡(jiǎn)介
Fisher–Yates shuffle 洗牌算法可以用于對(duì)數(shù)組進(jìn)行隨機(jī)排列，它的時(shí)間復(fù)雜度為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]
假定有一個(gè)數(shù)組a=[1, 2, 3, 4, 5, 6, 7, 8, 9]，數(shù)組長(zhǎng)度為n，打亂a中元素的具體迭代步驟如下：
生成一個(gè)[0, n-1]區(qū)間的隨機(jī)數(shù)k；將第k個(gè)元素和第n-1個(gè)元素進(jìn)行交換；進(jìn)行下一輪迭代，生成一個(gè)[0, n-2]區(qū)間的隨機(jī)數(shù)k，將第k個(gè)元素和第n-2個(gè)元素進(jìn)行交換， 迭代次數(shù)為n-1次：從n-1取到1；最終得到一個(gè)打亂的數(shù)組。
下表是一個(gè)數(shù)組的具體打亂過程，打亂后的數(shù)組是(9 4 8 1 2 3 5 6 7)
| 隨機(jī)數(shù) | 原數(shù)組 | 新數(shù)組 |
|---|---|---|
| 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實(shí)現(xiàn)
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[*]}
執(zhí)行效果：
$ 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
到此這篇關(guān)于shell實(shí)現(xiàn)Fisher–Yates shuffle洗牌算法介紹的文章就介紹到這了,更多相關(guān)shell Fisher–Yates shuffle洗牌算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
shell 中數(shù)學(xué)計(jì)算總結(jié)
shell中的賦值和操作默認(rèn)都是字符串處理，在此記下shell中進(jìn)行數(shù)學(xué)運(yùn)算的幾個(gè)特殊方法，以后用到的時(shí)候可以來看，呵呵2012-09-09
Shell腳本實(shí)現(xiàn)根據(jù)端口號(hào)kill相應(yīng)進(jìn)程功能
這篇文章主要介紹了Shell腳本實(shí)現(xiàn)根據(jù)端口號(hào)kill相應(yīng)進(jìn)程功能,本文相對(duì)簡(jiǎn)單,只有一句話,需要的朋友可以參考下2014-12-12
這篇文章主要介紹了Shell正則表達(dá)式驗(yàn)證IP地址,本文給出了多個(gè)方法,并分別給出實(shí)現(xiàn)代碼,需要的朋友可以參考下2015-05-05
最近很多同學(xué)問小編關(guān)于Linux命令的問題,小編今天主要介紹Linux里的tree命令,tree命令是一種遞歸目錄列表顯示命令,使用該命令可以以樹狀圖的形式列出一個(gè)目錄下所有文件內(nèi)容,本文給大家介紹gitBash中使用Linux中的tree命令,一起看看吧2023-11-11
Linux中shell腳本的執(zhí)行通常有4種方式，分別為工作目錄執(zhí)行，絕對(duì)路徑執(zhí)行，sh執(zhí)行，shell環(huán)境執(zhí)行。這篇文章主要介紹了shell腳本4種執(zhí)行方式 ,需要的朋友可以參考下2019-05-05
linux shell中實(shí)現(xiàn)循環(huán)日期的實(shí)例代碼
這篇文章主要介紹了linux shell中實(shí)現(xiàn)循環(huán)日期的實(shí)例代碼，文中還給大家提到了LINUX SHELL遍歷日期（指定輸入兩個(gè)日期）的實(shí)現(xiàn)方法，感興趣的朋友跟隨小編一起看看吧2018-09-09
shell腳本配合zabbix實(shí)現(xiàn)tomcat的故障自愈功能
這篇文章主要介紹了shell腳本配合zabbix實(shí)現(xiàn)tomcat的故障自愈,服務(wù)實(shí)現(xiàn)自愈的方式有通過shell腳本+定時(shí)任務(wù)的方式，藍(lán)鯨Pass故障自愈平臺(tái)，shell腳本+zabbix觸發(fā)器動(dòng)作，本文給大家詳細(xì)介紹，需要的朋友可以參考下2022-03-03
linux修改目錄和文件權(quán)限的簡(jiǎn)單命令解釋
這篇文章主要介紹了linux修改目錄和文件權(quán)限的命令使用,大家參考使用2013-11-11
Nginx和PHP-FPM的啟動(dòng)、重啟、停止腳本分享
這篇文章主要介紹了Nginx和PHP-FPM的啟動(dòng)、重啟、停止腳本分享,腳本中包含start、stop、reload、restart等常用的管理方法,并可以加入系統(tǒng)服務(wù)然后使用servicem命令管理,需要的朋友可以參考下2014-12-12
Linux下自動(dòng)刪除過期備份和自動(dòng)異地備份的腳本
這篇文章主要介紹了Linux下自動(dòng)刪除過期備份和自動(dòng)異地備份,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-09-09