跳到主要內容

陣列洗牌程式(shuffle array)

陣列如何把它的順序打亂,作出類似洗牌的效果,我一直都很頭痛,搞得非常的複雜。至從用了Ruby,Array物件包含shuffle方法之後,我就沒思考過陣列洗牌的問題了,反正Ruby幫我處理得好好的。

Ruby

# 52張牌的牌堆
poker = (1..52).to_a    # => [1, 2, 3, ... , 52] 
# 洗牌打亂
shuffled = poker.shuffle           # => [22, 32, 12, ...
# 也可以直接打亂原來的陣列
poker.shuffle!          # => [39, 47, 3, ...

Javascript

Javascript我就頭痛了,我得自己寫洗牌的方法。我在網路上找到了這個演算法,仔細看了之後,才知道原來洗牌可以這麼簡單:

// 原本for迴圈是一行程式,太難理解,這邊改寫成多行
function shuffle(o){
    for(var j, x, i = o.length; i;){
        j = Math.floor(Math.random() * i);

        // javascript的array是0-base
        // 所以迴圈第一次進入,--i後表示陣列最後一個位置。
        x = o[--i];
        o[i] = o[j]; 
        o[j] = x;
        // 以上三行代表以x為temp, o[i], o[j]做交換
    } 
    return o; //回傳陣列,我一開始也看錯看成回傳0
};

變數說明

  • 引數o: 將被洗牌的陣列
  • for迴圈內
    • i : 將會從陣列的最後一個位置,慢慢往前移到第一個位置(但移到第一個位置時for迴圈不執行,因為Javascript的數值0也代表false,會離開迴圈。0代表flase這點跟Ruby不一樣)
    • j : 將會被亂數選擇,選到要被交換的位置
    • x : 用來暫存o[i]的數值,幫助o[i]與o[j]做數值交換

就這樣從最後一個位置開始,依次往前隨機挑選一個位置與它交換(可能挑到自己,表示不交換),來達到洗牌的效果,陣列多大,就執行幾次,時間複雜度O(n),效率也不錯。 注意這邊傳入的陣列是call by reference,會修改原來呼叫方法時傳入的陣列,所以直接:

// 5張牌的牌堆
poker = [1, 2, 3, 4, 5];
shuffle(poker);
// poker 就直接被打亂了

如果不想打亂原來的牌堆,就稍微改寫一下,不要動到原來的陣列:

function shuffle(o){ //v1.0
    var ary = o.slice(0);
    for(var j, x, i = ary.length; i;){
        j = Math.floor(Math.random() * i);
        x = ary[--i], ary[i] = ary[j];
        ary[j] = x;
    }
    return ary;
};

這邊用到了一個小技巧slice(start, end),這是javascript用來複製陣列的一個區塊,指令開始與結束的位置,小技巧是如果傳入0,就直接複製整個陣列。如果你想說:

啊直接ary = o 不是更快

呵呵,我建議你從C的指標在開始複習一下。

C語言

使用C語言,改些小地方,C語言的rand()產生的是0 ~ RAND_MAX的一個數字,所以直接j = rand() % i;就行了。還有C語言的0也表示false的意思,大概只有Ruby跟大家不同,目前我只見過Ruby的0表示true。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int *shuffle(int *o, int length){
    int i,j,x;
    for(j, x, i=length; i;){
        j = rand() % i;
        x = o[--i];
        o[i] = o[j];
        o[j] = x;
    }
    return o;
}

int main(void) {
    srand(time(NULL));
    int i, poker[] = {1, 2, 3, 4, 5};
    shuffle(poker, 5);
    for(i=0; i&lt;5; i++)
        printf("%d ", poker[i]);
    return 0;
}

這邊我是用call by address的寫法,如果你不想改變原來的陣列。C語言有一堆記憶體的函式讓你用,你可以宣告一塊記憶體空間(malloc),然後記憶體複製(memcpy),之後傳入shuffle去洗牌

不建議在shuffle函式裡面宣告記憶體區塊,因為什麼時候要free掉記憶體很麻煩,交給呼叫他的函式去決定什麼時候free掉比較正確,shuffle函式就專心洗牌就好。

JQuery

在網頁上面,要把一些HTML的元件打亂,可以直接在JQuery裡面加個物件方法給他:

jQuery.fn.shuffleElements = function () {
    var o = $(this);
    // 這邊的for迴圈,使用原本的一行寫法
    for (var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
};

裡面那個for迴圈洗牌的演算法沒變。

至於一些基本的jQuery用法,jQuery.fn,可以直接取得jQuery的prototype,關於javascript的prototype是什麼,請至函式 prototype 特性觀看。這邊使用jQuery.fn就可以直接在jQuery的protoype裡面加入shuffleElements方法,然後就直接傳入一堆HTML元件讓他去洗牌,譬如你的網頁有一堆圖片,簡單一點就這樣:

var img = $("img").shuffleElements();
$("body").append(img);

這麼寫的話,可以簡單地把你網頁裡面的圖片全部洗牌之後,再全部放回<body>最下面。這邊主要是講洗牌,你可以改一改把它變成<ul>的順序之類的,或其他的應用。

留言

這個網誌中的熱門文章

HTML, CSS, 相對視窗或螢幕的高度與寬度

在 w3school.com 網站, CSS Units 有各種與寬度的表示法 以我使用的頻率來排序: px: 使用螢幕幾個像素(但是還要考慮Retina螢幕像素是一般螢幕像素的兩倍) %: 相對父層的大小比例 vh, vw: 相對於瀏覽器展示網頁區域的大小(不是整個瀏覽器的大小,沒包含瀏覽器的工具列,只有展示網頁的區域) vmin: vh, vw取最小值(另外還有vmax則是取最大值,但是目前IE跟safari不支援) px 與 % 很常用, vh , vw 與 vmin 是CSS3的新產物,表示相對瀏覽器展示頁面的大小 相對視窗大小 這邊先說明, vh , vw 與 vmin 只包含網頁顯示區域的長寬,不包含瀏覽器的工具列 先從dom的最根本講起好了,一份HTML文件,根是 <html></html> (雖然沒有嚴格規定,不寫也能顯示),然後這個根的父元件就是瀏覽器的網頁頁面顯示區 因此,如果對 <html></html> 宣告大小是 100% 就跟宣告 100vh 一樣,因為都是指瀏覽器的網頁頁面顯示區大小 這個範例是將html設定為100vh <html style="height: 100vh"> <head> <script src="https://code.jquery.com/jquery-1.11.1.min.js"></script> <script type="text/javascript"> console.log($('html').height()); </script> </head> </html> 這個範例是將html設定為100% <html style="height: 100%"> <head> <script src="https://code.jquery.com/jque...

安裝zsh + oh-my-zsh 出現 /usr/bin/env: zsh: 沒有此一檔案或目錄 (/usr/bin/env: zsh -: No such file or directory)

zsh 跟 oh-my-zsh 安裝完,可能會出現類似下面錯誤訊息,雖然他沒任何影響,不過我總覺得怪怪的 # 中文系統 /usr/bin/env: zsh: 沒有此一檔案或目錄 # 英文系統 /usr/bin/env: zsh -: No such file or directory 通常會出現這類的訊息,都是指令找不到。 這邊指zsh這個指令找不到,試試看輸入 which zsh 看看是不是沒有把zsh這個加到 $PATH 裡面,沒有的話加入就好了。 如果加入了一樣找不到,我trace了一下zsh的執行過程,通常都是跟 oh-my-zsh 的安裝順序錯了的時候才會發生。 這時編輯家目錄底下檔案 vim ~/.zshrc ,會看到 # 他先執行了oh-my-zsh.sh source $ZSH/oh-my-zsh.sh # 然而oh-my-zsh.sh已經在使用zsh這個指令了 # 這裡才把宣告路徑,所以當然zsh指令找不到 export PATH="/usr/kerberos/sbin:/usr/kerberos/bin:/usr/local/sbin:/usr/sbin:/sbin:/usr/bin:/bin:/root/bin:/usr/local/bin" 這時就把它們兩個對調一下就好了 # 像這樣把 export PATH 放到 source $ZSH/oh-my-zsh.sh 上面 export PATH="/usr/kerberos/sbin:/usr/kerberos/bin:/usr/local/sbin:/usr/sbin:/sbin:/usr/bin:/bin:/root/bin:/usr/local/bin" source $ZSH/oh-my-zsh.sh # 這樣oh-my-zsh.sh裡面就可以用zsh指令了 存檔後,登出再進來,他就可以正常使用zsh指令,不再出現這種錯誤訊息了