---
# System prepended metadata

title: 2025q1 Homework1 (lab0)

---

# 2025q1 Homework1 (lab0)
contributed by <WenHsuanYu>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
    
## 開發環境

```bash
❯ lscpu              
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 7 5800X 8-Core Processor
    CPU family:           25
    Model:                33
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             0
    Frequency boost:      disabled
    CPU(s) scaling MHz:   57%
    CPU max MHz:          5360.0000
    CPU min MHz:          550.0000
    BogoMIPS:             8400.39
    ...
❯ gcc -v             
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-linux-gnu/13/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 13.3.0-6ubuntu2~24.04' --with-bugurl=file:///usr/share/doc/gcc-13/README.Bugs --enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-13 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/libexec --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-libstdcxx-backtrace --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04) 
```
	
## 撰寫 queue.c

### q_new

使用 `malloc` 配置記憶體，並確認配置是否成功；接著，使用 `list.h` 中的`INIT_LIST_HEAD` 巨集初始化 `head`。
    
```c
/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}
```
    
### q_free
	
為了確認要釋放的記憶體對象，我們檢閱了 qtest.c 中使用 q_free 函式的地方，發現其操作的對象是 element_t 型別。這個型別內嵌了 struct list_head 型別的 list 成員，用於構成鏈結串列。

接著，我們利用 list.h 提供的 list_for_each_safe 巨集來安全地走訪鏈結串列中的每一個節點。在迴圈中，pos 會指向目前節點的 list 成員，而 safe 則會指向下一個節點的 list 成員。然後，我們透過同樣在 list.h 中定義的 list_entry 巨集，從 list 成員反向取得包含它的 element_t 節點的記憶體位址，最後再將該節點所配置的記憶體釋放。
    
```c
void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *pos, *safe;

    list_for_each_safe(pos, safe, head) {
        element_t *item = list_entry(pos, element_t, list);
        q_release_element(item);
    }

    free(head);
}
``` 
    
### q_size

首先檢查 `head` 指標是否為空。如果不為空，表示佇列至少包含一個空的佇列結構。接著，我們直接使用 `list.h` 提供的 `list_for_each` 巨集來遍歷鏈結串列中的每一個節點，並在走訪過程中記錄節點的數量。最後，函式會回傳所走訪的節點總數。

```c
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *pos;

    list_for_each(pos, head) {
        len++;
    }
    return len;
}
```
    
### q_insert_head

首先，程式會檢查 `head` 指標是否為空。如果 `head` 為空，表示佇列不存在，此時將中止後續操作。接著，程式會呼叫新增的 `q_new_element` 函式來配置 `element_t` 型別的記憶體空間，並將提供的字串複製到新配置的空間中，然後回傳這個新節點的記憶體位址。最後，透過 `list.h` 中提供的 `list_add` 巨集，將這個新節點插入到佇列的頭部。
    
以下是 `q_new_element` 函式實作：
    
```c
/* Create a new element */
static element_t *q_new_element(char *s)
{
    element_t *item = malloc(sizeof(element_t));
    if (!item)
        return NULL;

    item->value = strdup(s);
    if (!item->value) {
        free(item);
        return NULL;
    }
    INIT_LIST_HEAD(&item->list);
    return item;
}   
```

以下是 `q_insert_head` 函式實作：
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = q_new_element(s);
    if (!item)
        return false;

    list_add(&item->list, head);

    return true;
}
```

### q_insert_tail

首先，程式會檢查 `head` 指標是否為空。如果 `head` 為空，表示佇列不存在，此時將中止後續操作。接著，程式會重用 `q_new_element` 函式來配置 `element_t` 型別的記憶體空間，並將提供的字串複製到新配置的空間中，然後回傳這個新節點的記憶體位址。最後，透過 `list.h` 中提供的 `list_add_tail` 巨集，將這個新節點插入到佇列的尾端。
    
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = q_new_element(s);
    if (!item)
        return false;

    list_add_tail(&item->list, head);
    return true;
}
```

簡化程式碼和重複使用既有的程式碼 `q_insert_head` 函式改善可維護性和可讀性。
    
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert_head(head->prev, s);
}
```

### q_remove_head


首先，程式會檢查 head 指標是否為空，或者佇列本身是否為空。如果 head 為空或佇列為空，此時將中止後續操作。接著，程式會使用 `list.h` 中提供的 `list_first_entry` 巨集來取得鏈結串列的頭節點。然後，再透過同一個標頭檔提供的 `list_del` 巨集將該頭節點從鏈結串列中移除（注意：此操作僅將節點從鏈結串列中斷開，並未釋放其佔用的記憶體）。緊接著，程式會先檢查 sp 指標和 bufsize 變數，以確保有足夠的空間進行複製，之後，它會將剛才移除的節點中所儲存的字串複製到 sp 指標所指向的記憶體空間中，並最終回傳這個被移除的節點。
    
這邊的字串複製為了避免字串緩衝區溢位的問題，所以選擇自定義一巨集 [`strlcpy`](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 透過 `snprintf` 函式解決相關安全疑慮，不考慮使用 `strncpy` 函式，因為無法保證有終止符（即 '\0\')。
    
    
```c

#ifndef strlcpy
#define strlcpy(dst, sr, sz) snprintf(dst, sz, "%s", sr)
#endif

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *item = list_first_entry(head, element_t, list);
    list_del(&item->list);

    if (sp && bufsize)
        strlcpy(sp, item->value, bufsize);

    return item;
}
```

### q_remove_tail

在實做這個功能時，我很快就發現其程式邏輯與現有的 `q_remove_head` 函式非常相似，主要的差異只在於要移除的節點位置不同（一個是頭部，一個是尾部）。因此，為了提高程式碼的重用性並減少重複開發，我決定重複使用 `q_remove_head` 函式，並透過調整程式的移除位置來實現移除尾端節點的功能。
    
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    return q_remove_head(head->prev->prev, sp, bufsize);
}
```

### q_delete_mid
    
我們運用環狀雙向鏈結串列的「環狀」特性，同時從串列的頭部和尾部開始，每次都各自向前移動一個節點。考量到當串列的節點總數是偶數時，從頭尾兩端出發的兩個指標最終不會指向同一個節點，而是會彼此相鄰。因此，我們需要額外設定一個結束迴圈的條件：當這兩個指標所指向的節點彼此只差一個節點時，就停止走訪。基於 LeetCode 相關題目的處理方式，在這種頭尾指標相鄰的情況下，我們也選擇刪除相鄰節點的右節點。

    
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *left = head->next;
    struct list_head *right = head->prev;
    while (left != right && left->next != right) {
        left = left->next;
        right = right->prev;
    }
    list_del(right);
    element_t *item = list_entry(right, element_t, list);
    q_release_element(item);
    return true;
}
```
    

### q_delete_dup
    
在開發這個功能時，我首先確認輸入的鏈結串列已經是排序過的，因此不需要進行額外的排序操作，可以直接處理重複的節點。在這裡，我宣告了一個布林旗標變數 `has_dup`，用來記錄目前是否偵測到重複的節點；當有重複節點時，這個旗標會設為真（true），沒有重複時則為假（false）。此外，當 `has_dup` 從真變成假的時候，這表示我們剛處理完一個連續重複的節點群組，且目前的節點值已經和下一個節點的值不同，這時候可以直接刪除該重複節點群組中的最後一個節點，不需要再進行額外的檢查。
    
```c
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    element_t *curr, *safe;
    /* the last repeated node */
    bool has_dup = false;

    list_for_each_entry_safe(curr, safe, head, list) {
        // check if curr->value is equal to the next node value
        bool is_equal =
            &safe->list != head && !strcmp(curr->value, safe->value);
        if (is_equal || has_dup) {
            has_dup = true;
            list_del(&curr->list);
            q_release_element(curr);
            has_dup = is_equal && has_dup;
        }
    }

    return true;
}  
```
    
如下圖所示，原本值為 3 的空白節點是為了方便說明而保留下來的。當 curr 指向紅色的節點，而 safe 指向綠色的節點時，因為這兩個節點的值不相同，所以 is_equal 這個判斷會是 false。此時，由於先前已經發生過重複節點的刪除操作，has_dup 這個旗標變數仍然會保持為 true。這樣一來，程式就能夠正確地刪除最後一個重複的紅色節點。在完成刪除之後，我們也會立即更新 has_dup 旗標的值，將其設定為 false，以便正確追蹤後續的重複情況。
    
```graphviz
digraph g{
  rankdir=LR
  node [shape=record];

  n1 [label="{<data>1 |<ref>}"];
  n2 [label="{<data> |<ref>}"];
  n3 [label="{<data>3 |<ref>}" color=red style=bold];
  n4 [label="{<data>4 |<ref>}" color=green style=bold];
  n5 [label="{<data>4 |<ref>}"];
  n6 [label="{<data>4 |<ref>}"];

  n1 -> n2 [dir=both];
  n2 -> n3 [dir=both];
  n3 -> n4 [dir=both];
  n4 -> n5 [dir=both];
  n5 -> n6 [dir=both];
}
```
    
### q_reverse
    
主要的作法是運用 `list.h` 中提供的 `list_move` 巨集，將每次走訪的節點移動雙向鏈結串列的頭部，即走訪到的節點移動到 `head` 偽節點之後。

```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *it;
    struct list_head *safe;
    list_for_each_safe(it, safe, head)
        list_move(it, head);
}
```
    
### q_reverseK
    
我們宣告一個計數器變數 `count` 來記錄目前已經走訪過的節點數量。每走訪 `K` 個節點時，就使用 `list.h` 提供的 `list_cut_position` 巨集，將這 `K` 個節點從原來的鏈結串列中剪切下來，並暫時儲存到一個臨時變數中。接著，我們重複使用先前實作的 `q_reverse` 函式，針對這個長度為 `K` 的子鏈結串列進行反轉操作。最後，將反轉後的子鏈結串列重新串接回原鏈結串列中對應的位置，並且更新下一次要進行剪切的起始節點。
    
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;

    struct list_head *it, *safe, *begin;
    int count = k;
    begin = head;
    list_for_each_safe(it, safe, head) {
        if (--count)
            continue;
        LIST_HEAD(tmp);
        count = k;
        list_cut_position(&tmp, begin, it);
        q_reverse(&tmp);
        list_splice_init(&tmp, begin);
        /* The iterator will be changed */
        begin = safe->prev;
    }
}   
```
    
### q_swap
    
做了 `q_reverseK` 函式後，發現 `q_swap` 本質上就是 `q_reverseK` 函式的特例。當 `K = 2` 時，即達到 `q_swap` 的兩兩交換。
 
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    q_reverseK(head, 2);
}
```

### q_sort

`q_sort` 函式的實作，我採用了傳統教科書上常見的 `Top-down merge sort`。這個方法的概念是先將原始的鏈結串列遞迴地分割成兩個長度大致相等的子鏈結串列，這個分割過程會持續進行，直到子鏈結串列的長度變成零或是不存在為止。接著，再依照遞迴回溯的順序，逐步合併這些已排序的子鏈結串列。最終，兩個長度各半的已排序子鏈結串列會合併成一個與原始鏈結串列相同長度的已排序鏈結串列，這樣就完成了排序。

為了實現這個合併的步驟，我撰寫了一個 `q_merge_twolists` 函式。這個函式會接收一個 `flag` 參數，用來決定是要進行遞增排序還是遞減排序。在合併的過程中，它會比較兩個子鏈結串列中的節點，將符合排序條件的節點依序放置到一個暫時的 `tmp` 鏈結串列的尾端。當其中一個子鏈結串列的所有節點都處理完畢後，會將另一個子鏈結串列中剩餘的節點直接串接到 `tmp` 鏈結串列的尾部。最後，再透過 `list_splice_tail_init` 這個巨集，將排序好的 `tmp` 鏈結串列的內容接回到原始鏈結串列的 `head` 節點之後。
    
```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *left = head->next;
    struct list_head *right = head->prev;
    while (left != right && left->next != right) {
        left = left->next;
        right = right->prev;
    }
    struct list_head *mid = left;
    LIST_HEAD(r);
    list_cut_position(&r, mid, head->prev);

    q_sort(head, descend);
    q_sort(&r, descend);

    q_merge_twolists(head, &r, descend);
}
```

```c
void q_merge_twolists(struct list_head *l, struct list_head *r, bool flag)
{
    if (!l || !r)
        return;
    /* flag: 0 for descend and 1 for ascend */
    int ascend = flag ? 1 : -1;
    LIST_HEAD(tmp);
    while (!list_empty(l) && !list_empty(r)) {
        element_t *l_item = list_first_entry(l, element_t, list);
        element_t *r_item = list_first_entry(r, element_t, list);
        if (strcmp(l_item->value, r_item->value) * ascend >= 0) {
            list_move_tail(&l_item->list, &tmp);
        } else {
            list_move_tail(&r_item->list, &tmp);
        }
    }
    list_splice_init(&tmp, l);
    list_splice_tail_init(r, l);
}
```

### q_ascend
    
這個方法的主要思路是從鏈結串列的尾部開始，反向掃描到頭部。刪除條件是如果某個節點存在右側節點，且該右側節點的值嚴格小於目前節點的值。從尾部往頭部的角度來看，就是我們首先處理末尾節點，接著處理末尾節點的前一個節點（也就是倒數第二個節點）。刪除條件會變成倒數第二個節點的值大於或等於末尾節點的值，那麼這個倒數第二個節點就需要被刪除。反之，如果倒數第二個節點的值小於末尾節點的值，我們就往鏈結串列的頭部方向前進一個節點。這樣的處理方式可以確保在我們每次選取一個節點時，它之後的所有節點（往尾部方向）的值都一定大於目前節點的值。
    
不考慮從鏈結串列的頭部開始掃描到尾部的原因是很難知道某節點的右側節點中是否存有一節點滿足刪除條件，實作上比起從尾部掃到頭部更加麻煩。

```c
/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    int count = 1;
    element_t *item = list_last_entry(head, element_t, list);
    while (item->list.prev != head) {
        element_t *prev_item = list_last_entry(&item->list, element_t, list);
        if (strcmp(item->value, prev_item->value) < 0) {
            list_del(&prev_item->list);
            q_release_element(prev_item);
            continue;
        }
        count++;
        item = prev_item;
    }

    return count;
}
```   
### q_descend

主要思路跟 q_ascend 一樣，差別只在於使用 `strcmp` 比較兩節點值的判斷，從 $<$ 變成 $>$。
    
```c
/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    int count = 1;
    element_t *item = list_last_entry(head, element_t, list);
    while (item->list.prev != head) {
        element_t *prev_item = list_last_entry(&item->list, element_t, list);
        if (strcmp(item->value, prev_item->value) > 0) {
            list_del(&prev_item->list);
            q_release_element(prev_item);
            continue;
        }
        count++;
        item = prev_item;
    }

    return count;
}
```
    
### q_merge
    
由於此函式限制不能額外配置記憶體，並且合併所有佇列後，只有第一個佇列需要存放最終合併後的雙向鏈結串列，其餘的佇列變成空佇列。但要注意的是，這些空的佇列不需要將其成員 `q` 指標指向 `NULL`，否則在外部後續釋放這些佇列所配置的記憶體時，可能會發生記憶體洩漏的問題。因此，後來的做法是宣告一個 `queue_contex_t` 型別的指標 `end`，這個指標作為判斷合併迴圈結束的標記（考量到環狀鏈結串列的特性）。同時，我們也使用一個 `size` 變數（初始值設為第一個佇列的長度）來累加所有要跟第一個佇列合併的佇列的長度總和。接下來，就是重複呼叫 `q_merge_twolists` 函式來進行雙向鏈結串列的合併操作，每次合併的結果都會存放到第一個佇列中。並且，在每次成功合併後，我們會將第二個被合併的佇列移動到佇列的環狀雙向鏈結串列的尾部。
    
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return q_size(list_first_entry(head, queue_contex_t, chain)->q);

    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
    int size = q_size(first->q);

    queue_contex_t *second =
        list_entry(first->chain.next, queue_contex_t, chain);
    queue_contex_t *end = NULL;

    while (second != end) {
        size += q_size(second->q);
        q_merge_twolists(first->q, second->q, descend);

        if (!end)
            end = second;

        list_move_tail(&second->chain, head);
        second = list_entry(first->chain.next, queue_contex_t, chain);
    }

    return size;
}
```
    
## 亂數研究和 Shuffle 實作

先新增 Shuffle 命令到 cmd_list
    
[e0d69c5](https://github.com/WenHsuanYu/lab0-c/commit/e0d69c53dc0b79ceb5aa86c23ce56bbd70ab641d#diff-4bea8c1c8a7201344362702328f624bc857916de5db17073078e8a3d2bf781e8R1123)
    
```diff
 static bool do_show(int argc, char *argv[])
 {
     if (argc != 1) {
@@ -1096,6 +1120,7 @@ static void console_init()
                 "");
     ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
                 "[K]");
+    ADD_COMMAND(shuffle, "Shuffle the queue", "");
     add_param("length", &string_length, "Maximum length of displayed string",
               NULL);
     add_param("malloc", &fail_probability, "Malloc failure probability percent",
```
    
接著按照作業說明使用  Fisher–Yates shuffle 演算法來實作洗牌，然而，考量到鏈結串列不像陣列那樣能夠直接隨機存取特定節點，我們無法直接套用該演算法。為了解決這個問題，我們採取了間接指標的方式：先配置一段與佇列（queue）長度相同的記憶體空間。
    
```c
struct list_head **pos = malloc(sizeof(*pos) * len);
```

完成記憶體配置後，我們會逐一拜訪鏈結串列中的每個節點，並將其在記憶體中的實際位址儲存到我們剛才配置的空間。這樣一來，我們就得到了一個包含所有節點位址的「陣列」，方便後續的隨機操作。
    
```c
struct list_head *node;
    list_for_each(node, head)
        pos[i++] = node;
```
    
接下來進入 `Fisher–Yates shuffle` 演算法的核心實作階段。由於亂數的產生範圍不一定能被待處理的佇列長度整除，這可能會導致機率偏差。因此，我們採用「拒絕取樣」的方法：如果取樣到的亂數值不符合需求範圍，我們會重新取樣，直到取得合適的亂數，藉此消除機率偏差，確保洗牌的公平性。

完成洗牌後，我們會依據打亂後的節點位址順序，重建環狀雙向鏈結串列。最後，釋放先前配置的記憶體空間，並回傳 true，表示洗牌操作成功。

```c
    /* Fisher-Yates shuffle */
    for (i = len - 1; i > 0; i--) {
        int idx;
        do {
            idx = q_random() & INT_MAX;
        } while (idx >= INT_MAX - (INT_MAX % (i + 1)));
        idx %= i + 1;

        struct list_head *temp = pos[i];
        pos[i] = pos[idx];
        pos[idx] = temp;
    }
    
    /* Rebuild the list */
    INIT_LIST_HEAD(head);
    for (i = 0; i < len; i++) {
        list_add_tail(pos[i], head);
    }
    
    free(pos);
    return true;
```

### 統計方法驗證 `shuffle`
 
透過作業說明提供的 python 程式來分析是否均勻分佈，程式本身會執行 1000000 次洗牌，並統計每種排列方式的出現頻率次數。

| 排列 | 出現次數 | 預期次數 |
| ---- | -------- | -------- |
| 1234 | 41862    | 41666    |
| 1243 | 41576    | 41666    |
| 1324 | 41716    | 41666    |
| 1342 | 41779    | 41666    |
| 1423 | 41643    | 41666    |
| 1432 | 41545    | 41666    |
| 2134 | 41465    | 41666    |
| 2143 | 41367    | 41666    |
| 2314 | 41460    | 41666    |
| 2341 | 41544    | 41666    |
| 2413 | 42020    | 41666    |
| 2431 | 41523    | 41666    |
| 3124 | 42034    | 41666    |
| 3142 | 41944    | 41666    |
| 3214 | 41633    | 41666    |
| 3241 | 41671    | 41666    |
| 3412 | 41477    | 41666    |
| 3421 | 41700    | 41666    |
| 4123 | 41617    | 41666    |
| 4132 | 41510    | 41666    |
| 4213 | 41428    | 41666    |
| 4231 | 41824    | 41666    |
| 4312 | 41745    | 41666    |
| 4321 | 41917    | 41666    |
---
                        
計算出來的皮爾森卡方檢定為： 20.115，透過[線上工具](https://www.socscistatistics.com/pvalues/chidistribution.aspx)計算 P 值，P 值為 0.63 大於顯著水準(alpha)所設定的 0.05，因此統計檢定的結果不拒絕虛無假說，觀察樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻 $H_{0}$。

