---
title:2023 年資訊科技產業專案設計課程 作業二
---

# 2023「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業二
>#### 貢獻者：鋒美食-Tastii
>🗿：interviewer
>🤓：interviewee
>
>#### 影片
>* [鋒美食-Tastii: Homework2 (漢)](https://youtu.be/9I0261Ts0kU)

### 46. [Permutations](https://leetcode.com/problems/permutations/)

🗿：(開場...)
🗿：你知道我們公司最核心業務資料探勘，我想要你設想一個情境
🗿：假設今天你拿到一份dataset，裡面有100多筆features，你有一些先備知識讓你能夠從這些features中提取出你認為比較有用用處的特徵，而有時候要建立一些機器學習模型訓練時，要先將某些特徵的權重給設定，我希望你可以先簡單想一個方法快速將這些特徵的優先順序給定出
🤓：根據Oscar你的說法，我已經將所需要的feature都提取出來了
🤓：那其實我首先要做的就是排列出這些已經選取出來的feature
🤓：請問我可假設這些資料是1~n的整數，以代替特徵名稱嗎?
🗿：沒有問題
🤓：假設擷取出來的特徵為[1,2,3]，那我會獲得的排列順序就是
* [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,2,1]、[3,1,2]

🤓：這樣我打算直接實作排列
🤓：首先排列最開始想到的就是用Recursive的方法進行
🤓：先假設所有我需要的特徵都存在一個nums vector中，之後輸出排列結果會存在二維result vector中
🤓：然後我要使用swap的方法，我需要一個for loop每次交換nums中其中兩個元素位置
🤓：例如以上面[1,2,3]為例子，我在loop中會產生[1,2,3]是由nums[0]和nums[0]交換位置的結果、[2,1,3]是由nums[0]和nums[1]交換位置的結果、[3,2,1]是由nums[0]和nums[2]交換位置的結果，3種排列
🤓：而在這些排列中我也必須去swap他們元素中的位置，所以這邊用到recursive，在上面的loop中從nums[0]為起點去和後面的元素交換位置，而進到resursive後，我則變成由nums[1]開始往後去交換，所以進到recursive後起始的交換位置就+1，這很合理因為看前面例子產生的3種結果，開頭分別是1、2、3，所以我往後的交換就不考慮開頭的元素

void permutateRecursive(vector<int> &nums, int begin, vector<vector<int>> &result){
    for(int i = begin ; i < nums.size() ; i++){
        swap(nums[begin],nums[i]);
        permutateRecursive(nums,begin+1,result);
        swap(nums[begin],nums[i]);  // *
    }
}

🤓：最後一個swap我標註*號的地方，這邊要再將剛剛swap過的元素換回來，這樣後續才不會錯亂掉
🤓：然後我還必須要有終止條件，也就是把排列好的結果存起來

void permutateRecursive(vector<int> &nums, int begin, vector<vector<int>> &result){
    if(begin >= nums.size()-1){
        result.push_back(nums);
        return;
    }
    
    for(int i = begin ; i < nums.size() ; i++){
        swap(nums[begin],nums[i]);
        permutateRecursive(nums,begin+1,result);
        swap(nums[begin],nums[i]);  // *
    }
}

🤓：最後呼叫該程式，並把結果存起來

 vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    permutateRecursive(nums,0,result);
    return result;
    }

🗿：我覺得你解釋的蠻清楚的，那我想和你探討一下這方法的缺點
🗿：先請你分析一下這方法的時間空間複雜度
🤓：時間複雜度是O(n!*n)，因為有n!個排列結果，而每次要將一個排列結果存入result需要花費O(n)的時間
🤓：空間複雜度是O(n!)，因為有n!個排列結果要存
🗿：那排列過後的結果有n!種，你這種方法是 Full Search，在訓練模型的時候是不可能把n!都訓練一次來比較結果的，那請問你有沒有方法可以降低訓練次數的
🤓：(thinking...)
🤓：那一樣假設我已經挑出了一些有用的feature，但我還想要從這些feature中更進一步的篩出哪些才是真正有用的
🤓：我一樣想用greedy的方法把這些feature 測試過一輪，但我又要大幅減少訓練模型的次數
🤓：首先我先設定一個模型訓練合格分數為best，再來從我挑出來的features中選一個或是隨機一個放到一個result集合中，接著，使用result中的的特徵和全部features中排序第二的特徵訓練一個模型用交叉驗證計算出分數
🤓：如果模型的結果優於前面best，則將這個排序第二的feature放入result集合中，並將best更新
🤓：後面則不斷重複上面動作直到所以features都測驗完成
🤓：這樣我就可以更進一步挑出更好的features
🤓：然後從這些更優良的features的集合result中，我再做回歸分析找出最佳權重
🗿：喔ok，那這方法明顯比一開始的permutation好上許多
🗿：(ending...)

### 作業二 初步檢討 & 改進
#### interviewer side
* 題目設計還有待加強

#### interviewee side
* 因為想要和permutate扯上關係，題目設定有點奇怪，其實大可以跳過前面實做permutate的部分，直接進行後半段就好。
* 之後試試看用C寫
* 畫圖舉例的時候我想表達的是nums[0]nums[1]，但是我用的例子又是數字1 2 3，這樣解釋起來很容易混淆，舉例失當，我應該將例子用A B C 去帶，這樣會好很多
* 最後一段口頭說明的部分其實也可以在google document上畫圖出來說明

### 作業二 我給其他學員評價
* 主要觀察REACTO有沒有做到
* 題目與答案是否合理，例如我有發現一個人的題目基本上是經典sort的變形，但他解答時卻直接使用C++ stl的sort來解