Lambda Enumerable Combinations(排列組合C函數)

2020-03-09

175
0
2020-03-10

題目出處 Arcade > Thr Core > 92 Strings Crossover

將crossover定義為2個同長度字串間的運算:字串A與字串B做了此運算後將得到一個長度也相同的字串result，並且所有result[i]不是與A[i]相同就是與B[i]相同(隨機選取)

現在給定一個string[] inputArray, string result，求inputArray中有多少組合可能經由crossover運算得到result?

註1:(A,B)與(B,A)只算一種組合
註2:組合中不能包含同一元素2次，除非在inputArray中有多個該元素

範例:
For inputArray = ["abc", "aaa", "aba", "bab"] and result = "bbb", 
the output should be stringsCrossover(inputArray, result) = 2
因為("abc","bab")、("aba","bab")這2組可做出"bbb"

如果從集合方面想就是排列組合的C函數，要在所有inputArray取2的組合中找出有幾組可以做出result

或是直接2層迴圈一組組檢查是否可以做出result也可以

暫且不管用哪一個方法，先把是否可以做出result的判斷寫出來

看到Enumerable要做同位置元素處理就會想到Zip，但是這邊有3個，要使用linq原本的Zip就要做2次

這邊因為能確保長度相同，換了一個方法來做3個Enumerable的處理 (更多的方法參考stackoverflow)

// s1與s2是否可以做出r
bool canMakeResult(string s1, string s2, string r)
{
    return Enumerable.Range(0, s1.Length).All(i => s1[i] == r[i] || s2[i] == r[i]);
}

之後就是要計算有幾組了，以迴圈寫大概就是這樣的架構

for(int i=0; i<inputArray.Length; i++)
{
    for(int j=i+1; j<inputArray.Length; j++)
    {
        cnt += canMakeResult(inputArray[i], inputArray[j], result) ? 1 : 0;
    }
}

想到了集合，就嘗試以C函數來寫，目前想到了遞迴的方法

IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> a, int take)
{
    if (take == 0)
        return new T[][] { new T[]{ } };
    return a.SelectMany((x,idx) => Combinations(a.Skip(idx+1), take-1).Select(r => new T[] { x }.Concat(r)));
}

之後測試了一下C4取2

之後套用到原題目中，完成

int stringsCrossover(string[] inputArray, string result) {
    return Combinations(inputArray,2).Count(x => canMakeResult(x.First(), x.Last(), result));
}

這樣如果情境為要取3個一組也不用包成3層迴圈了

參考:

https://stackoverflow.com/questions/14639481/merge-multiple-lists-into-one-list-with-linq

https://codesignal.com/

回首頁