【CS50x(2022)】ProblemSet3 - Tideman 題解(Bubble sort)

這是目前在 CS50x 課程中遇到的最難的題目了，如果不把思考邏輯好好整理一遍，下次再回顧應該還是要花很多時間理解一遍。

前言

這一篇是使用 Bubble sort 方式解題，如果想使用其他排序法，可直接使用以下連結，除了排序法之外的內文都是一樣的。

Tideman 題解(Selection sort)。

題目說明

題目出自 Harvard CS50x 課程第三週作業練習，可先看看題目說明再往下看。

在一般的選舉活動中，通常是採取相對多數決或是絕對多數決，也就是候選人只要得到一定數目選票即可獲得勝利。然而 Tideman method 是採用完全不同的邏輯。Tideman method 或稱 Ranked pairs 是指在每一張選票上寫上對所有候選人的意向排序，把所有選票上的候選人兩兩互相比較得出一個符合多數人的排序結果，而排名第一的人就是最後的獲勝者。

目前這樣簡單的介紹可能還有點抽象，接下來或做個詳細的說明。

程式結構及邏輯

先來看看題目提供的邏輯架構：

#include <cs50.h>
#include <stdio.h>

// 定義候選人數目為 9 
#define MAX 9

// 一個 9x9 的表格，每一格紀錄選票排序上，候選人[i] > 候選人[j]的選票有幾張。
int preferences[MAX][MAX];

// 一個 9x9 的表格，每一格紀錄 boolean 值，說明候選人[i]和候選人[j]之間的箭頭關係是否被鎖定。
bool locked[MAX][MAX];

// 定義新的資料型別 "pair"，這個型別會記錄 winner 和 loser 在 array 裡的 index(integer)
typedef struct
{
    int winner;
    int loser;
}
pair;

// Array of candidates
string candidates[MAX];             // 一個紀錄所有候選人的 array
pair pairs[MAX * (MAX - 1) / 2];    // 一個紀錄所有 pair 的 array

int pair_count;
int candidate_count;

// Function prototypes
// 作業需要完成的 6 個 function
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

int main(int argc, string argv[])
{
    // 確認 terminal 提供的參數是否正確
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // 把 terminal 提供的候選人名字寫進 candidates 列表裡
    candidate_count = argc - 1;
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i] = argv[i + 1];
    }

    // 初始化 locked 表格，讓每一格都是 false 
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // 取得每一張選票內容
    for (int i = 0; i < voter_count; i++)
    {
        // 定義選票排序 array: ranks[i] 是投票者排序第 i 名的候選人 index
        int ranks[candidate_count];

        // 取得每一個排序的候選人 index
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        // 將選票結果更新到 preferences 表格
        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

題目要求完成 6 個 function 來執行投票/開票作業，接下來會針對每個 function 做詳細說明。

vote

投票者每在選票上填入一個名字就會執行一次，將填入的名字放進紀錄選票的陣列 ranks[] 中。這個函式共引入了 3 個參數：

bool vote(int rank, string name, int ranks[])
int rank        // 目前填入的名字在選票排序的第幾位
string name     // 填入的名稱
int ranks[]     // 記錄這張選票所有排序的 array

首先，為了排除廢票狀況，要先檢查填入的名字是否存在候選人清單中，如果存在則填入 ranks[] 清單並回傳 true；反之則回傳 false。這邊用到一個 library： strcmp() 來比對字串是否相同，所以要記得在檔案最上方加入 #include <string.h> 。

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    for (int i = 0; i < candidate_count; i++)
    {
        // Check if vote to person in candidates list
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

record_preferences

每填完一張選票，就將這張選票每兩位候選人間的意願關係填入 preferences 表格中。這邊就要先解釋原始題目line8 的變數 int preferences[MAX][MAX] 了。int 代表這個陣列填入的資料型別是整數，後面的 [MAX] 則是代表表格的列數和欄數，而 MAX 的值在 line5 設定為 9。

preferences[row][col] 二維表格

preferences[row][col] 是一個二維陣列，假設 [row] 和 [col] 都是 3 ，表格畫起來如下圖：

candidates[index]	Alice [0]	Bob [1]	Charlie [2]
Alice [0]	0	Alice > Bob 的選票張數	Alice > Charlie 的選票張數
Bob [1]	Bob > Alice 的選票張數	0	Bob > Charlie 的選票張數
Charlie [2]	Charlie > Alice 的選票張數	Charlie > Bob 的選票張數	0

選票意向解讀

選票	說明(比對上圖)
1. Alice 2. Charlie 3. Bob	1. Alice 贏過 Bob 和 Charlie，所以 preferences[0][1] 和 preferences[0][2] 各加 1 2. Charlie 贏過 Bob，所以 preferences[2][1] 加 1。 3. Bob 沒贏過任何人，不對表格做任何改變。

來看看函式的 prototype：

1
2
3

void record_preferences(int ranks[])
void         // 沒有回傳值
int ranks[]  // 使用 candidates[] 的 index 來紀錄選票中候選人排序的陣列

如同上面舉的例子，當完成一張選票 ranks[] 時，依序迭代每個順位的候選人，將他們的比較結果填入 preferences 表格中。i 代表選票的第 i 順位，j 則代表 i 以外的其他候選人。

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // Person of each rank on ballot
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // Plus number of voters who prefer i over j
            preferences[ranks[i]][ranks[j]] += 1;
        }
    }
    return;
}

add_pairs

在投完所有票及更新 preferences 表格後，從表格中挑出所有獲勝的組合。假設投完票後的意向表格如下：

candidates[index]	Alice [0]	Bob [1]	Charlie [2]
Alice [0]	0	3	1
Bob [1]	1	0	2
Charlie [2]	3	2	0

交叉比對確認兩候選人間的勝敗後，將候選人 index 記錄進 line23 pairs 陣列裡。前面有定義過 (line14-19)， pair 這個型別的陣列裡面會記錄 winner 跟 loser 的 index(要注意先後順序)。原始題目(行號)

依照上表範例：

Alice 對 Bob 的票數 preferences[0][1] > preferences[1][0]，所以將 {0, 1} 放入 pairs 陣列。
Alice 對 Charlie 的票數 preferences[0][2] < preferences[2][0]，所以將 {2, 0} 放入 pairs 陣列。
Bob 對 Charlie 的票數 preferences[1][2] == preferences[2][1]，沒有勝者，所以不加入 pairs。

綜上所述， add_pairs 函式只要迭代整個表格找出勝者加入 pairs 即可。特別注意的是，因為我們只要找出勝者，所以不對 if (preferences[i][j] == preferences[j][i]) 的情況做任何處理。

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            // If one way arrow (i over j)
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
        }
    }
    return;
}

sort_pairs (Bubble sort)

Bubble sort 的原理是和相鄰的項目做比較，並和相鄰項目交換位置，直到完成升冪或降冪的排序。舉例說明，有一個陣列 array[5] = {2, 4, 5, 3, 1}，如果我要把它由小到大排序：

// 原始陣列
array[5] = {2, 5, 4, 3, 1};
// Step1: index[0] 跟 index[1] 比較，若遇到較小的就交換位置
{2, 5, 4, 3, 1} 

// Step2: index[1] 跟 index[2] 比較，若遇到較小的就交換位置
{2, 4, 5, 3, 1}

// Step3: index[2] 跟 index[3] 比較，若遇到較小的就交換位置
{2, 4, 3, 5, 1}

// Step4: index[3] 跟 index[4] 比較，若遇到較小的就交換位置
{2, 4, 3, 1, 5}

// 重複 step1~4 直到排序完成

會看到較大的數字會像泡泡一樣逐漸向右浮出。

題目要求將 pairs 陣列由大到小排列。比大小需要數值，但 pairs 陣列紀錄的只是勝者和敗者，我們可以拿獲勝的力度來為每對候選人作排序。

獲勝的力度指的是「覺得A候選人勝過B候選人的票數」。舉前面 add_pairs範例表格來說， Alice 勝過 Bob 的力度是 3。

接著，就如同 bubble sort 說明一樣，取出 pairs 陣列中相鄰的 pair strength (preferences[winner][loser])進行比較並互相交換，最後完成降冪排列。

void sort_pairs(void)
{
    for (int i = pair_count - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            int current_pair_strength = preferences[pairs[j].winner][pairs[j].loser];
            int next_pair_strength = preferences[pairs[j + 1].winner][pairs[j + 1].loser];
            if (current_pair_strength < next_pair_strength)
            {
                pair temp = pairs[j];
                pairs[j] = pairs[j + 1];
                pairs[j + 1] = temp;
            }
        }
    }
    return;
}

lock_pairs

這個步驟的目的是為了在所有的 pairs 之間做取捨。如果直接採用所有的 pair，選舉結果可能會出現:
A > B 、 B > C 、 C > A 這種找不到最終勝利者的情形。而 lock_pairs 是將 pair_strength 由大到小分別做檢查，如果沒有變成死循環的 pair 就採用(lock)，變成死循環的 pair 就棄用。

備註：此部分說明參考【nicknapoli82/cs50_Tideman_cycle-explanation.md】

舉例來說，現在有的候選人和 sorted pairs 資料如下:

1 2	`Candidates[4] = [a, b, c, d] Sorted Pairs = [{d, a}, {a, b}, {b, c}, {c, a}, {d, b}, {d, c}]`

之後將 sorted pairs 依序拿出來做檢查，如果不是死循環則生成排序鏈。
sorted pairs[0] : d > a ，lock ，排序鏈 d > a 。
sorted pairs[1] : a > b ，lock ，排序鏈 d > a > b 。
sorted pairs[2] : b > c ，lock ，排序鏈 d > a > b > c 。
sorted pairs[3] : c > a ，形成死循環，棄用此 pair，排序鏈維持 d > a > b > c 。
sorted pairs[4] : d > b ，lock ，排序鏈維持 d > a > b > c 。
sorted pairs[5] : d > c ，lock ，排序鏈維持 d > a > b > c 。

此時，詳細排序鏈應該長這樣：

		a
	↗	↓
d	→	b
	↘	↓
		c

最後寫出的 locked[4][4] 表格如下，有單向箭頭的為 true：

candidate[index]	a [0]	b [1]	c [2]	d [3]
a [0]	false	true	true	false
b [1]	false	false	true	false
c [2]	false	false	false	false
d [3]	true	true	true	false

依照上面的說明，lock_pairs function 的邏輯為：檢查是否有死循環，沒有則為 true。(前面已將整張表格預設為 false，所以如果 locked[winner][loser] = false ，不做任何處理。)

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    for (int i = 0; i < pair_count; i++)
    {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;

        if (!cycle_occurred(winner, loser))
        {
            locked[winner][loser] = true;
        }
    }
    return;
}

接下來則是規畫檢查死循環的步驟，新建一個 function cycle_occurred。

因為我們是依照 pair_strength 的順序來鎖定的，所以檢查的方式就是把 winner 和 loser 反過來查表，看看會不會和目前已經鎖定的 pairs 形成死循環，如果 locked[loser][winner] == true 就表示造成死循環。

另外，前面有提到排序鏈長這樣 d > a > b > c ，但其實它包含了 d > a 、 d > b、 d > c 這三個路線，如下圖:

		a
	↗	↓
d	→	b
	↘	↓
		c

如果我要確定 d > c 會不會造成死循環，同時也必須要對其他路線做確認，所以使用 for loop 來迭代每個候選人。

// Check if cycle occurred
bool cycle_occurred(int winner, int loser)
{
    if (locked[loser][winner] == true)
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[loser][i] && cycle_occurred(winner, i))
        {
            return true;
        }
    }

    return false;
}

print_winner

在完成 lock_pairs 經過步驟後，會完成下面這張表格。要找出最後贏家的辦法，就是確認一個候選人「沒有輸給任何人」，也就是候選人的 loser column 全部為 false，如下表綠字表示：

candidate[index]	a [0]	b [1]	c [2]	d [3]
a [0]	false	true	true	false
b [1]	false	false	true	false
c [2]	false	false	false	false
d [3]	true	true	true	false

// Print the winner of the election
void print_winner(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        int false_count = 0;

        for (int j = 0; j < candidate_count; j++)
        {
            // Check if candidates[j] has arrow to cadidates[i]
            if (locked[j][i] == false)
            {
                false_count++;

                // if no arrow to candidates[i], find winner
                if (false_count == candidate_count)
                {
                    printf("%s\n", candidates[i]);
                }
            }
        }
    }
    return;
}

而為什麼不用「贏過除了自己的任何人呢」(也就是 candidate[i] row 除了自己全部為 true)？
因為我們在一開始就將表格預設為 false ，而平手情況也是 false 。向下圖這種情況，會有兩個贏家，而 a > d 或 d > a 都會是 false。

a
\|\|	↘
d	→	b
	↘	↓
		c

小結

完成版的 code 在這裡。

這個題目是目前課程作業中最難的一個，光題目的理解就花了很多時間也閱讀很了多資料(遞迴之類的…)，但挑戰不同排序法還是很有趣。在寫這篇題解的過程中也嘗試了不同寫法，發現導致沒有 100% pass 的例外狀況(平手)。整體來說，這是個很考驗邏輯思考的作業!

相關文章: CS50x(2022)

文章內容如有錯誤，歡迎留言討論！

CS50

#CS50x #C #Algorithms

本 Blog 上的所有文章除特别聲明外，均採用 CC BY-SA 4.0 協議，轉載請註明出處！

【CS50x(2022)】Complexity and Big O Notation Previous

【CS50x(2022)】ProblemSet3 - Tideman 題解(Selection sort) Next