Algorithm筆記 8 - 小孩分群演算法

分群問題

如何將一群n個小孩根據某條件p來分成最少的群呢?

最直接(笨)的方法就是把所有的可能分法都窮舉出來，亦即找出一個set的所有subset，當然空集合是一個合法的subset。

最小限度來說，如果要把n個物體分到相異2群中 (某群可以完全是空)，至少就要花上2^n次方次的對條件p的篩選，因為對每個小孩來說都有2種選法，所以總共是2^n個選法，也就是running time O(2^n)。

然而分成相異兩群的所有方法只是窮舉所有分群法中的一個subset，所以O(2^n)是窮舉法的下限running time，也就是OMEGA2(^n)。

這是一個exponential (變數n在指數) running time algorithm，執行時間隨n變化將極為陡峭劇烈，我們必須尋求更好asymptotic running time的方法。

Greedy approach

解決問題通常將之轉成數學model，這有助找出特性與轉化成簡單問題的方式。

假設這個條件p為 每群中的小孩年齡相差不能超過一歲

一個數學上的模型是轉成數線，數線上的點(值) 代表每個小孩的年齡:

同群中任何兩人不能相差超過一歲的限制，就用一個長度為1的線段來表示，所以每個線段涵蓋的點，就是一個滿足條件p的同一群人，以下是其中一種分法 (分成四群):

如果一個點同時被兩個線段涵蓋，那並不構成model上的任何意義，因為此點只會屬於其中一群。

當然也可以這樣分 (更好一些，分成三群):

能不能有一個greedy algorithm?

首先我們必須要找出一個safe move，也就是某個optimal solution的第一步，假設以下敘述是一個safe move:

長度為1的線段最左緣，如果重合了最左邊的點(年紀最小者)，則這是一個safe move。

記得我們必須證明safe move成立，否則不能使用greedy approach，因為不見得是optimal solution。如何證明上述描述是一個safe move?

greedy algorithm

如果我們把任意一個optimal solution的第一條線段 (group 1)的左緣，拉到與數線上最左邊的點重和的話，原本在線段1涵蓋的點的總數不會改變，所以group 1的人數也不會改變:

上圖中第3個點雖然同時被涵蓋在第一條紅線和第二條藍線中，但是並沒有什麼影響，它仍然屬於group 2的點。 由於紅線位置的改變並不影響optimal solution最後的output，所以這個移動方式是一個optimal solution，所以是一個safe move。

有了safe move，根據greedy algorithm的實作方式，我們把剃除掉第一群的點 (上圖紅線中的前兩個點)，剩下的所有點就構成了一樣的分群問題，就是一個subproblem。

所以這是一個greedy algorithm可以找到optimal solution的問題。演算法如下:

首先所有的小孩的年紀被map到一個sorted array{x1, x2, ... , xn}，R是最後的分法集合，指標i從第一個點x1開始檢查。

先列出先把這個線段的涵蓋範圍l和r設定為x1和x1+1，+1的意思是線段長度。
然後inner while loop找出下一個xi，使得此xi > r，亦即找出下一個不在此線段涵蓋範圍內的點，當作下一個subproblem的最左邊的點。

pseudo-code大概就這樣，來分析它的running time。

Polynomial time 

這個演算法從頭到尾走了n次，所以是O(n)，不過這是建立在我們先把x1..xn排序過的前提下，如果沒有排序的話，必須要進行排序，則目前已知最好的排序演算法的running time為O(nlogn)。

所以整體running time = O(nlogn) + O(n) = O(nlogn)。

相對於OMEGA(2^n)的 naiive algorithm的改善相當的大!

Algorithm筆記 7 - 最少加油次數演算法分析

承筆記6，我們嘗試來寫此問題的解決演算法。

這個演算法接受三個參數：

x是一個array，包含從出發點A, 終點B, 和所有加油站的位置：

n是個加油站的array index
L是加滿油可以跑得最大距離

所以演算法寫起來相當簡單：

不過這是一個O(n^2)的演算法，因為有nested loop，而內外loop各是跑最多n次。

藉由不同implementation的方式，我們可以將之變成O(n)的演算法：

public static int minRefills(int[] positions, 
                             int secondLastGasStationIndex, 
                             int farestDistanceCanGo) {
    int numRefills = 0;
    int currentPosition = 0;
    int lastRefill = currentPosition;

    while (currentPosition <= secondLastGasStationIndex) {

        if (positions[currentPosition + 1] - positions[lastRefill] <= farestDistanceCanGo )
            currentPosition += 1;
        else {
            lastRefill = currentPosition;
            numRefills += 1;
        }

    }

    return numRefills;
}

以上的演算法沒驗證過，但大概就是這樣。

這邊的教訓是implementation optimization是很有影響（廢話一句）。

Algorithm筆記 6 - Greedy Algorithm

一般演算法課程都會先介紹greedy系列，因為這跟人類的天性比較相近（短視近利？！），但這個策略事實上在某些應用中的確是很有效的解題方式。

Greedy strategy牽涉到三個步驟：

1. 如何做一個符合（假設存在）optimal solution的貪婪決定？（稱為safe move)
2. 如何把大問題劃成許多相同的較小問題 (稱為subproblem)
3. 如何持續不斷做1和2

怎樣加最少次的油？

以car-fueling problem為例，假設有從A到B路上有以下幾個加油站：

每次加滿油可以跑400 km，怎麼加油才會最少次呢？

1. 如果以greedy的含義來看的話，應該要往加最少次的方向去思考，則合理的一個greedy choice嘗試就是只在能跑得最遠能到達的加油站加油。

2. 假設採用1的greedy strategy在某個加油站G加油，則剩下的路程就變成一個subproblem，因為是一模一樣的問題，只是出發點不是A而是G。

3. 持續不斷把剩下的路程做1. 和 2.的步驟。

Safe Move需要證明！

我們要證明在每次能到達最遠距離的加油站加油是一個safe move。

假設從A 到 B有最少次加油的optimal solution解決方案，而其中第一次選的加油站為G1, 而G為離A能到達的最遠的加油站。

第一種可能G和G1重合，則得證。

剩下一種可能必然是G1離A比較近，因為我們已經定義G是離A最遠能到達的加油站。
假設我們在G1加油之後，下一個在optimal solution中要加油的是G2。

此時又有三種可能：
1. G在G1和G2中間：

此時如果要在G2加油的話，我們可以不選G1為第一個加油站，而選G為第一個加油站，因為在G1加滿油可以抵達G2的話，代表在G加滿油一定可以抵達G2，因為G1到G2的路程比G到G2來得遠。

所以如果用G代替G1當作第一個加油站的話，也是一個optimal solution，因為此solution的總加油次數不變。得證。

2. 第二種可能是G2在G1和G中間：

但這是不可能的，因為如果真是這樣，那我們完全可以選G2為第一個加油站就好，這樣整體加油次數會比原本的optimal solution少一次，這違反假設，不成立。

另外我們甚至可以選G為第一個加油站，因為G2到下一個加油站G3的距離大於G到G3的距離，所以在G加滿油一定可以抵達G3，整體加油次數也比optimal solution少2，違反假設，不成立。

3.  G2和G重和，一樣違反假設，不成立，原因與2.理由一樣。


所以我們證明了G一定是optimal solution的第一個加油站

Scala筆記 22 - 說說For

for在Scala裡面有點難掌握，有必要詳細的講一下：

1. 最簡單的form

compiler會翻譯成 (e1要有implement map method才行)：

這沒什麼疑問

2.  一個generator + 一個filter

compiler會翻譯成 (e1要有implement withFilter method才行)：

withFilter類似filter的功用，但是是lazy evaluation，換句話說不會即刻回傳filtered collection，而是先註記這個collection即將要被filter，如果collection去做map或是flatmap等動作時，就會先做此預告的filtering。

注意if f後面有一個 ; s，所以這個filter f是有順序性的，不是永遠擺在最後，而是看你要在哪一個loop level做filtering。

3. 2 generators

compiler會翻譯成 (e1要有implement flatMap, e2 要impelemt map method才行)：

每個e1的element x 被map成|e2|個collection，然後flatten。
所以相當於nested loop，outerloop執行 |e1| 次，inner loop執行 |e2|次（假設s沒有其他的generator）


以上三者可以當成基礎元件來解讀一個Scala for "loop"。

4. pattern matching in for

這是我在Anagrams的作業中有用到的技巧，不過我還是第一次看到等號的expression在generators中出現？！

generator中的pattern matching其實是對 collection的filter：

不過在generators中可以寫入assignment就有點奇怪了，找更多資料再來update這篇。

Algorithm筆記 5 - 一些解題的思考方式

剛做完Algorithmic Toolbox這門課的第一個assignment，還真的被跟Pisano period相關的某一題難住了，有點出乎意料之外，趕快趁熱把一些經驗談寫下來，希望之後用得到：

(以下的題目，Java grader要求在1.5秒內要pass所有的test）

計算小的Fibonacci Number

第一題沒啥特別，就是要讓我們知道不要根據題目的數學定義直接轉換成code，因為這可能是最沒效率的事，見我筆記2。這邊可以用簡單的dynamic programming來解決問題，由於grader只要求能在時間內完成Fib(45)的數就可以，所以沒什麼問題。

找出較大的Fibonacci數中的個位數字 (最大到Fib(10^7))

這一題其實就要引入一個觀念：轉化與簡化題目。由於計算fibonacci數字是O(n^2) runtime，所以我們不可能直接去計算Fib(10^7)，然後將之除以10來找個位數字。但是因為我們只關心個位數字，所以只要計算每個Fib(n)的個位數字就好，十位數字以上的我們不關心，這樣就可以避免大數字的計算，但實際asymtotic time我也不確定，我猜是O(n)。

一樣用簡單的dynamic programming來計算Fib(n):

private static int calc_fib_mod10(int n) {

    int[] F = new int[n+2];
    F[0] = 0;
    F[1] = 1;

    for (int i = 2; i <= n; i++)
        F[i] = (F[i-2] + F[i-1])%10;

    return F[n];
}

計算兩數最大公因數GCD (a,b 兩數分別最大到2*10^9)

這題也只是讓你練習筆記2中講的概念：先利用數學關係把題目簡化過一遍，這樣大大省略計算時間。O(log(a*b))

計算兩數最小公倍數LCM (a, b 兩數分別最大到2*10^9)

最小公倍數可以簡化成 a*b/GCD(a,b)，因為
a = GCD(a,b) * x
b = GCD(a,b) * y
LCM(a,b) = GCD(a,b)  * x  * y = (a * b) / GCD(a,b)

所以asymptotic runtime應該和GCD(a,b)一樣為 O(log(a*b))

計算大Fibonacci數 Fib(n) 除以m的餘數 (1≤𝑛≤1018,2≤𝑚≤105)

這一題就是我卡關的題目，主要是沒意識到要把計算限縮在餘數就好，因為這個input 已經太大了，沒把計算限縮在餘數的話，即便利用題目中提示的Pisano period簡化計算，也絕對跑不動。

這題其實就是用了上面幾題帶來的解題觀念！綜合應用之～

/*1 <= n <= 10^18 < Long.MAX2 <= m <= 10^5
(a + b) % m === (a % m + b % m) % m */
private static long getFibonacciHugePisano(long n, long m) {
    if (n <= 1)
        return n;

    long beforePrevious  = 0;
    long previous = 1;
    long a = -1;
    long current = -1;

    for (long i = 2; i <= n; i++) {
        current = (beforePrevious + previous) % m;

        if (a == 0 && current == 1) {
            long period = (i + 1) - 2;
            long reductionN = n % period;
            return getFibonacciHugePisano(reductionN, m);

        }
        else {
            a = current;
            beforePrevious = previous;
            previous = current;
        }
    }

    return current;
}

計算Fibonacci數字連加的和的個位數字 (0 ≤ 𝑛 ≤ 1014)

這應該有兩種做法，第一種（我沒嘗試的）就是把計算限縮在個位數來算Fib(0) + Fib(1) + ... + Fib(n)的和，但我懷疑是否能通過grader的1.5秒時間限制？這感覺上是O(n^2)。

第二種就是找看這個數列有無規則？還真的有，原來SumFib(n)的個位數隨著n變大，每60次會循環一次，所以只要找出這60個數字，之後用查表法就超快：

private static final int PERIOD = 60;
private static int[] LastDigitOfFibSums = new int[] {
        0, 1, 2, 4, 7, 2, 0, 3, 4, 8, 3, 2, 6,
        9, 6, 6, 3, 0, 4, 5, 0, 6, 7, 4, 2, 7,
        0, 8, 9, 8, 8, 7, 6, 4, 1, 6, 8, 5, 4,
        0, 5, 6, 2, 9, 2, 2, 5, 8, 4, 3, 8, 2,
        1, 4, 6, 1, 8, 0, 9, 0};

private static int getFibonacciSumLastDigit(long n) {
    return LastDigitOfFibSums[(int)(n % PERIOD)];
}

這題的啟示就是，執行觀察各種input的結果，是否有可能有規律性，一但有規律性就非常容易解決問題。

上一題的Pisano period無法有一個modulo m 的 P(m)的函數，只能在loop裡面找重複的時機，當然就沒有這一題執行快了。不考慮 n % Period的話，O(1)。

找出Fibonacci數列中部分和 𝐹𝑚 + 𝐹𝑚+1 + · · · + 𝐹𝑛  的個位數字 (0 ≤ 𝑚 ≤ 𝑛 ≤ 1018)

這一題乍看之下，跟上一題很像，但可惜其output沒有規律性。不過跟上一題還是有關係，因為它可以寫成上一題的式子：

(F(3) + F(4) + F(5) + F(6) + F(7)) % 10 

= (F0 + F1 + F2 + .. + F7 - (F0 + F1 + F2)) % 10

= (SumFib(7) - SumFib(2)) % 10

要能跟getFibonacciSumLastDigit扯上關係，必須要證明

SumFib(7)%10 - SumFib(2)%10 == getFibonacciSumLastDigit(7) - getFibonacciSumLastDigit(2)

的確是可以，以下：

if x > y,

(x - y)% 10 == (x%10 - y%10), if x%10 >= y%10

(x - y)% 10 == x%10 - y%10 + 10, if x%10 < y%10

所以我們可以簡單地用上一題的output來實作本題：

private static long getFibonacciPartialSumLastDigit(long from, long to) {
    

    int x = getFibonacciSumLastDigit(to);
    int y = getFibonacciSumLastDigit(from-1);
    if (x >= y)
        return x - y;
    else        return x - y +10;

}

結論

如果一個問題能以數學來model最好，因為通常有規律性或是簡化轉化問題的機會！

Probability筆記 1.1 - 如何解讀Probability

MIT補充

機率有幾個面向：
1.純數學，這就單純是符號運作，沒有解讀必要

2. 頻率 frequency：通常是“無限次”實驗中某事件發生的次數佔比。不過通常描述生活中事件無法用頻率和實驗來類比。

3. 信念程度 Belief: 機率比較適合解讀成人們對某事件可能發生的相信程度。但這似乎是主觀的？不是，機率學提供系統思考架構，但是能否客觀描述一事物，則決定在我們model是否正確，而統計學正是用來彌補機率學對model選擇之不足，藉由觀察得到大量data來找出最適合的model。

以下是三者關係：

不過這是用機率去解釋uncertainty ，世界不一定是這樣運作就是了（例如確實有因果關係人們卻找不到，只好用機率論來假設和預測）。

Probability 筆記1 - Sample space

disjoint events

event就是一個包含某些outcomes的集合，若說某兩個events are disjoint，意思是這兩個event中的outcome完全沒有彼此重複的。如果outcome a發生在event A，則outcome a不可能在disjoint event B中發生。A與B沒有交集。

一個最顯著的例子就是event A以及其補集complement of A。

Event

一個event就是一堆可能發生的outcome的集合，通常用set notation來表示。例如投擲兩顆公正的骰子X and Y，和為10的event：

{  (i, j) | 1 <= i, j <= 6 && i + j = 10 }

以上是event的set描述式，我們也可以展開描述式填入實值：
{ (4,6),  (5,5), (6,4) }

Sample space

sample space是包含所有outcomes的set，但是以set notation的寫法並沒有一定型態，因為可以把sample space分成好幾個events，而所有這些events的聯集就是sample space，所以以擲銅板無限次為例，以下的兩種寫法都表現出同一個sample space:

n個outcome的sample space所形成的所有possible events (所有subset) 數目，是2^n個，因為一個subset可能有或沒有某一個outcome，這樣就是一個tree的branch，以tree來想的話就比較簡單。

MIT課程補充

sample space的set成員要有以下性質：

mutually exclusive outcome:永遠只有一個會發生，不會同時有兩個outcomes發生

collectively exhaustive: sample space擁有所有可能發生的outcomes

right granularity: 這是指sample space只要包含跟問題有關的outcomes，例如值一個銅板的sample space應該是下圖上者，而非下者，雖然兩者都包含mutually exclusive / collectively exhaustive outcomes

Algorithm筆記 4 - 常用的lograithm equation

另外定義如下：

Recall that logan is the power to which you need to raise a in order to obtain n.

Algorithms筆記 3 - Big-O

Actual Runtime

我們無法預測一個program的實際執行時間，因為那牽涉到了執行程式的軟體環境和硬體架構等的所有細節條件，所以我們想要知道的是，我們的program是不是scalable? 想知道當input size變大的時候，我們的執行時間會怎麼變化？

不過可以確定，通常不同電腦執行程式的速度差異只會是一個常數級的差別，（不過有時候常數很大...例如一般PC 和超級電腦的差別）。

Asymptotic Runtime

一個program的asymptotic runime在n非常大的時候，會有天差地遠的差別（遠超過常數級別的差異）：

Asymptotic runtime就是在看一個演算法的runtime成長趨勢如何。

Big-O Notation

f is Big-O of g的意思是f這個runtime 函數被g bound在下，所以g至少是c*f。正確定義如下：

如果f <= c * g，而h和g有相同最高次項，我們通常會把O(g)簡化成O(h)，因為h和g有相同的asymptotic runtime（只有常數倍數的差異）。

注意事項！

Big-O只有在比較演算法的asymptotic runtime時有效，但是如果實際input n size並不大，那不見得要選asymptotic runtime小的演算法，因為可能過了某個input size k之後才有runtime優勢，而常用的input size可能遠小於k。

另一個要注意的是，兩個演算法即便都是同樣的O(g)，可是常數倍數差異可能很大（即便只差兩倍也是很大），這時後當然要選常數項越小者，因為實際跑起來就是有倍數的差距。

Fibonacci asymptotic analysis

(1)

這是O(n)，因為每個memory cell可能要被初始化成0，而每個初始化的動作應該是個固定常數runtime，所以是O(1)，做了n次，就是O(n)


(2)

簡單的assignment動作一定都是constant runtime，所以是O(1)


(3)

loop部分牽涉到每個iteration要做i <= n以及 i++的operation，所以是n*O(1) = O(n)。
loop body乍看應該要是O(1)，但是這邊分析成O(n)是因為F[i]的數其實是跟著n長大的，fibonacci number有可能會大到一個machine word不能表達，所以addition operation所花的時間會隨著n增加，所以分析成O(n)，這是比較特別的地方


(4)

這沒有疑問是O(1)

所以這個Euclidean Fibonnaci asymptotical runtime =

我之前以為loop body是O(1)，所以以為整體應該是O(n)，看來錯了，所以naive recursion版本的fibonacci會比O(n^2)更慢!

Algorithms筆記 2 - GCD /Fibonacci 說明演算法的差異很大

Fibonacci

Fibonacci本身就是一個recursion，所以學過遞回的人直覺上會寫成和數學式相符合的recursive program:

不過這個事實上重複計算了很多recursions！所以非常慢（正確的running time要用master theorem才能估計出）。

反而沒學過遞迴的人寫出的直覺iterative program可以在linear time (應該是asymptotically n^2 runtime) solve:

這個等於是用了額外的記憶體F array來換取縮短執行時間

最大公因數GCD

最大公因數如果很天真直覺地用for loop來測試1到a+b的話：

雖然是linear time algorithm，但是應該有更好的方法？ （其實上面的for loop應該從a+b開始往下跑比較快）

要改良的方法是發現更多的數學上的關係（euclidean gcd lemma)：

所以我們可以快速縮減每次input到gcd()的a,b值：

根據lemma寫成的program，是一個recursive program，執行時間相當於log(a*b)，非常大的改進：

wow....是不是很有趣啊？！

Algorithms 筆記1: Stress Test

完成了Coursera Scala Specialization系列的第一門課之後，也來上一下之前沒看過的UCSD資料結構和演算法系列。之前不論是學校學的還是工作後學的，忘光光了吧！

這門課算是蠻實作入門的，先從實際的program執行告訴你演算法的好壞有顯著的影響，接著告訴你要怎麼debug你的演算法：stress test。

stress test主要是一個實驗組，一個對照組來跑隨機建立的input data。對照組是我們已知（應該）正確的演算法，我們藉由跑同一組input來檢視我們（實驗組）的program output是否正確，不過可能會出現對照組output是錯誤的情況，這時候也要修正對照組的程式。

stress test是一個無窮迴圈的測試，每次iteration都產生隨機的input data，但由於是利用pseudo-random generator，所以其實可以重現每次測試的input data。

測試的順序建議如下：

1. 手動測試number overflow cases，因為如果對照組也有overflow的問題，很有可能你們得出一樣的答案，但非正確
1.5 手動測試corner cases: 最大與最小可接受的value / size
2. 手動測試大input size，看所耗時間如何，這用來找出小input size能夠多大來跑得多次iteration
3. 小input size /小 input value
4. 小input size / 大 input value
5. 大input size / 大 input vale


在工作中好像不常使用stress test，主要是看什麼性質的application。非核心部分通常用不到吧！

Coursera: Functional Program Design in Scala 感想

這原本是Martin Odersky在Coursera開的一門免費課，但終究免費MOOC的商業模式是失敗的，所以在Coursera往盈利方向前進的路上，多數課程都變成沒有免費的certificate，而且也不能access graded assignments。這門課也不例外，原本兩門長課被分割成了Scala Specialization的前三門課，外加了一門新的Spark課程，以及一個Capstone project。

話說免費的certificates有意義嗎？我個人感覺是有，因為這是修課過後的證明，唯一走過留下的痕跡。老實說要修完一門這種難度的MOOC課程的人是佔比很少的，因為花了不少腦力與時間啊！MOOC修完幾乎沒有什麼立即的利益（除非你的工作本來就需要用到這門知識），所以完成率都相當的低落，如果連免費的certificate都沒有，對我個人已經沒有任何吸引力。我會把certificate拿來放在Linked-in的profile上，證明我是個life-long learner。

所以這也是我想要付費買Cousera Scala Specialization的原因，除了學習新的知識之外，就是為了這個certificate。付了錢之後真的會很有動力完成它！我想這也是免費MOOC不容易達到的事情。

這門課是之前的Scala課的一半內容，而且內容完全一模一樣，這也帶出了是否MOOC的內容可以重複利用的問題？隔了幾年之後，理論上應該要加上新的東西吧？畢竟Martin的Scala書也針對了新版的Scala補上一些東西，事先錄影好的課程也應該要有補充。

上了第二次，還是非常好的經驗，是programmer接觸functional programming很好的敲門磚。繼續註冊了第二門課！

Scala筆記 21 - 組合搜尋以及N-Queens Problem

N-Queens Problem

西洋棋盤上的皇后可以直吃, 橫吃, 斜吃，所以有人無聊想找出在nxn棋盤上可以同時擺n個皇后但不會互相殘殺的方法？

一種簡單的擺法就是，依照row順序來擺，擺完之後檢查有沒有column/diagonal衝突？

如果每種擺法用一個list表示，每個element的list index當作棋盤的row index，而element的值就是column index:

solution = List(
last_row_column_index,
..
..
first_row_column_index)

上圖的List(0,3,1)的意思是List(row2_col0, row1_col3, row0_col1)
(註：後擺上的棋子放在list最前面，應該是為了scala list cons方便的關係）


最終要找出一個set，包含所有的解法：
all solutions = Set(
solution1,
solution2,
.
.
solution
)

利用For-Yield來找combinations

def queens(n: Int) = {

  def placeQueens(k: Int): Set[List[Int]] = {
    if (k == 0) Set(List())
    else      for {
        queens <- placeQueens(k - 1)
        col <- 0 until n
        if isSafe(col, queens)
      } yield col :: queens
  }

  placeQueens(n)
}

他假設我們已經知道利用placeQueens這個helper function放k-1個皇后在nxn棋盤上，那我們要怎麼放第k個皇后？

在for中，每個iteration我們都檢查某個 placeQueens(k-1)回傳的set of solution list (type List[Int]) 中的某個solution，這個solution已經放了k-1個皇后在前k-1個row，下一個row應該放在哪一個column呢？

所以for的第二個generator就是 0到n-1的所有的column index來檢查，是否isSafe?
如果滿足isSafe的column index ，就把這個column index append到這個solution list的最前面。

for會yield出一個collection，type會是跟第一個generator的collection同樣，也就是Set[List[Int]]。

如何寫isSafe?

def isSafe(col:Int, queens:List[Int]) : Boolean = {
  val row = queens.length
  val qrows = (row - 1 to 0 by -1) zip queens
  qrows forall {
    case (r,c) => col != c && math.abs(col-c) != row - r
  }

}

這邊稍微有點tricky，可以trace看看。


N-Queens的演算法說明了怎麼長出某個list的所有subset，不錯的練習。

Scala筆記 20 - For...yield

如果要對一個list做nested loop能做到的是，通常我們需要寫filter, map和flatten：

def sumIsPrime(list:List[Int]) =
  list.flatMap( x => (list map ( y => (x,y) ))) filter{ case (x:Int,y:Int) => (x<y && isPrime(x+y)) }

Scala更抽象化了這個邏輯，模仿了imperative language的for loop，以下的例子可以改寫成for statment:

list filter( x => x>3) map (x => x*x)

for (elem <- list if elem > 3 ) yield elem*elem

在可讀性上是有改進了。

for 的參數包括了 generator-filter sequence:

• generator: pattern <- collection
• predicates: if (...)

for的參數如果用{ } 匡起來，則可以寫成multi-line generators/filter，（否則需要 ; 隔開generators)：

for (elem <- list 
     if elem > 3 ) yield elem*elem

或是這個nested loop:

Scala筆記 19 - Scala collection hierarchy

Vector

scala vector是用java array implement的shallow tree，第一層超過32個element的時候，就會轉化成32*32的capacity tree，以此類推長大：

跟list不同的是，list access elements需要的時間proportional to index n in the list，而vector的話因為是一個shallow tree，access某個element的時間視它存在於哪一層而定：

另一個vector優於list的地方在於因為是用array implement，所以element都是adjacent to each other in memory，有利於現代的memory cache技術。

何時使用list或是vector? 這取決於你的access pattern。
當你要寫一直取head，然後丟入tail到recursion的時候，用list為佳，因為list取head為constant time，而vector需要log(N)。但是如果要做bulk operation例如map, filter, fold之類的，用vector會有較少的access time。

另一個list方便的地方在於可以insert element在either head or tail:

xs :+ x
x +: xs

Scala collection hierarchy

事實上list和vector都是scala collection中的一員：

Java Array/String 不在此中，但是都可以implicitly use Scala Seq functions，應該是因為Seq都用generics impelemt的關係。


Scala Range是一個順序性數字的Seq:

Sequence operations

以下是一些有用的：

其中flatmap比較特別，他把一個seqeunce的element先map到另一個sequence，然後在flatten:

"ABC" flatMap( s => List(s.toLower,s) ) //res0: String = aAbBcC

利用scala sequence，我們如何從兩個數列xs ys中找出所有的pair combination?
假設xs = List(1, 2,.....M)
ys = List(1, 2, ... , N)

這個直覺上應該用flatmap function：

def combination(M:Int, N:Int) : IndexedSeq[(Int,Int)] =
  (1 to M) flatMap (x => ( (1 to N) map(y => (x,y))))

Pattern matching function value

如果我們要implement一個vector scalar product，一開始會直覺寫成：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( (x,y) => x*Y )

不過這個不會compile過，因為 zip出來的sequence element type不是pair，所以要寫anonymous function (或稱為function value)的時候，不能寫成(x,y)，要用單一的變數來承接：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( x => x._1 * x._2 )

這會比較不直覺，所以Scala又提供了另一個sysntatic sugar：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map{ case (x,y) => x * y }

這其實是以下的完整語法的省略：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( x => x match { case (a,b) => a * b })

這樣清爽多了！

實作isPrime with High-level sequence functions

按照數學定義的話，要檢測一個數n是不是質數，要看1以及n以外但是在之間的數，是否能被n整除：

def isPrime(n:Int):Boolean =
  (2 until n) forall( x => n%x != 0)