# 第 14 周作業講解
[TOC]

## [2024 - 無聊的小明](https://neoj.sprout.tw/problem/2024/) (遞迴解)

### 解題思路
看個例子：
- 排列 123
- 紀錄「可使用的數字」
- 一開始三個數字都可使用
- 選擇一個數字後就不能再使用
- 選擇 1 後可使用的數字就剩 2 3
- 每一層的選法都是從當前可使用的數字中小的開始選
- 選到沒有數字可以使用時就輸出


遞迴問題：
- 大問題：排列 n 個可使用的數字
- 小問題：把一個數字選出來後，排列剩下的 n - 1 個數字
- 終止條件：沒有可使用的數字時，直接輸出
- 為了能輸出所選擇的數字，我們還要**按照順序**紀錄「目前選了哪些數字」

### 程式框架

- 使用一個陣列來記錄可以使用的數字
- `usable[3]` 表示 3 這個數字可不可以使用
- 使用另一個陣列來記錄目前所選擇的數字
- 宣告一個遞迴函數，傳入「目前要排第幾位數字」和「最多可以選幾個數字」
- 這樣判端終止條件比較方便
- 為了方便，位數從左到右分別是 0、1、2、3...

bool usable[10] = {0};        // 可以使用的數字
int current_number[10] = {0}; // 目前所選擇的數字

void permutate(int cur_bit, int max_n)  {
}

### 判斷終止條件
- 如果目前已經選了 n 個數字，那就可以直接輸出了，因為一定沒有數字可以選了
- 輸出時，如果第 0 位 (最左邊的數字) 是 0，就跳過不輸出，直接 return
- 將 `current_number` 中的數字一個個輸出

if (cur_bit == max_n) {
    if (current_number[0] == 0)
        return;

    for (int i = 0; i < max_n; i++)
        cout << current_number[i];
    cout << endl;
    return;
}

### 拆分問題
- 從 0 開始找，如果當前的數字可以使用，就把它放到已選的數字中，並且標記爲不可使用
- 傳入下一層的函數，繼續排列後面的數字
- 下一層排完後，把當前的數字重新標記爲可以使用

for (int i = 0; i < 10; i++) {
    if (usable[i]) {
        current_number[cur_bit] = i;      // 放入目前所選擇的數字中
        usable[i] = false;                // 標記為不可使用

        permutate(cur_bit + 1, max_n);    // 排下一位

        usable[i] = true;                 // 重新標記為可以使用
    }
}

### 完整程式碼

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool usable[10] = {0};
int current_number[10] = {0};

void permutate(int cur_bit, int max_n) {
    if (cur_bit == max_n) {
        if (current_number[0] == 0)
            return;
        
        for (int i = 0; i < max_n; i++)
            cout << current_number[i];
        cout << endl;
        return;
    }

    for (int i = 0; i < 10; i++) {
        if (usable[i]) {
            current_number[cur_bit] = i;
            usable[i] = false;

            permutate(cur_bit + 1, max_n);

            usable[i] = true;
        }
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        usable[t] = true;    // 標記爲可以使用
    }

    permutate(0, n);         // 排第 0 位，最多排 n 個數字
}

## [2024 - 無聊的小明](https://neoj.sprout.tw/problem/2024/) (STL解)

### 解題思路

- 標準函式庫中的 [next_permutation](https://en.cppreference.com/w/cpp/algorithm/next_permutation) 函數可以把一個 vector 中的數字轉成下一個排列，例如輸入的 vector 是 `{2, 1, 3}`，呼叫該函數可以把這個 vector 變成 `{2, 3, 1}`
- 如果當前的排列是最後一個排列（如：`{3, 2, 1}`），該函數會回傳 false
- 標準函式庫中的 [sort](https://en.cppreference.com/w/cpp/algorithm/sort) 函數可以把 vector 由小排到大

搭配上面提到的兩個函數，我們可以構思出這樣的解法：
- 先把輸入由小到大排
- 不斷的輸出 vector 中的值並將它排成下一個排列
- 重複直到 next_permutation 回傳 false
### 程式框架

sort(a.begin(), a.end());

do {
    if (a[0] == 0)
        continue;

    for (auto t : a)
        cout << t;
    cout << endl;
} while (next_permutation(a.begin(), a.end()));

### 完整程式碼

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto &t : a)
        cin >> t;

    sort(a.begin(), a.end());

    do {
        if (a[0] == 0)
            continue;

        for (auto t : a)
            cout << t;
        cout << endl;
    } while (next_permutation(a.begin(), a.end()));
}

## [448 - 麻將排序問題](https://neoj.sprout.tw/problem/448/)
### 解題思路
- 用數字來表示牌
- 排序只在乎大小關係，所以每張牌的數字你想怎麼定都可以，只要大小關係對了就行
- 可以把餅（Ｂ）、條（Ｔ）、萬（Ｗ）當成單位:
- 1B = 1
- 1T = 10
- 1W = 100
- 大字 EE, SS, WW, NN, CC, FF, BB 就分別是 1000 ~ 7000
- 排序時就將牌名轉成數字後做比較

### 程式框架
根據上面的邏輯，寫出一個函數來轉換牌名與數字：

int getLevel(string &str) {
    int level = 0;
    if (isdigit(str[0])) {
        int d = str[0] - '0';
        switch (str[1]) {
            case 'T':
                d *= 10;
                break;
            case 'W':
                d *= 100;
                break;
        }
        level = d;
    } else {                // 大字
        int d = 1;
        switch (str[0]) {
            case 'E':
                break;
            case 'S':
                d = 2;
                break;
            case 'W':
                d = 3;
                break;
            case 'N':
                d = 4;
                break;
            case 'C':
                d = 5;
                break;
            case 'F':
                d = 6;
                break;
            case 'B':
                d = 7;
                break;
        }
        level = d * 1000;
    }
    return level;
}

而在排序時，可以使用 STL 的 sort 函數，為了讓他按照我們的意思排序，我們要自訂一個比較函數，用來比較兩個字串：

bool cmp(string &a, string &b) {
    return getLevel(a) < getLevel(b);
}

- 這個比較函數回傳值的意義可以想成：當他回傳 true 時，a 在前、b 在後的順序是正確的
- 如果他回傳 false，代表 b 應該要放在 a 前面

那在呼叫 sort 函數時，把我們的 cmp 放第三個參數傳進去即可

sort(cards.begin(), cards.end(), cmp);

### 完整程式碼

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int getLevel(string &str) {
    int level = 0;
    if (isdigit(str[0])) {
        int d = str[0] - '0';
        switch (str[1]) {
            case 'T':
                d *= 10;
                break;
            case 'W':
                d *= 100;
                break;
        }
        level = d;
    } else {
        int d = 1;
        switch (str[0]) {
            case 'E':
                break;
            case 'S':
                d = 2;
                break;
            case 'W':
                d = 3;
                break;
            case 'N':
                d = 4;
                break;
            case 'C':
                d = 5;
                break;
            case 'F':
                d = 6;
                break;
            case 'B':
                d = 7;
                break;
        }
        level = d*1000;
    }
    return level;
}

bool cmp(string &a, string &b) {
    return getLevel(a) < getLevel(b);
}

int main() {
    int n;
    cin >> n;

    vector<string> cards;
    cards.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }

    sort(cards.begin(), cards.end(), cmp);

    for (int i = 0; i < n; i++) {
        cout << cards[i];
        if (i != n - 1)
            cout << ' ';
    }
    cout << endl;
}