Haskellで組み合わせ
Haskellを使ってリストの中から任意の要素数の組み合わせをとる処理を考える。
2要素の場合
とりあえず2要素の場合はなんとなく感覚的に出来た。
--combはcombinationの意 comb [] = [] comb (x:xs)=[[x,y]| y <- xs] ++ comb xs main=do print $ comb [1..4] -- > [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
n要素の場合
任意の要素を取り出す場合の処理になると急にややこしくなる。
要素5個のリストから3つを取り出す組み合わせのツリーを考えると以下の様になる。
-------------------- 1-2-3 -4 -5 -3-4 -5 -4-5 -------------------- 2-3-4 -5 -4-5 -------------------- 3-4-5
図になってない為分かりにくいが破線(----) 毎に横向けのツリーだと思う事にする。
空白の列は上と同じという事。（やっぱ後で図にしようか。。。）
各ツリーのルート要素（上の場合1と2と3）が元々のリストの要素数に応じて再帰的に増えていき最終的に結合する事になる。
なので2要素を取り出す場合と同じように
[一つのツリーを表すリスト] ++ [再帰で別のツリーを表すリスト]
という構造になるはず。
次に一つのツリーに着目すると取り出す要素の数nに応じて、上の図で列の部分（ツリーの深さ）が再帰的に増えるのでこの部分をどうするかがポイント。
深さ4のツリーだとルート要素を除いた時、その下に深さ３のツリーがある事がわかる。同様にその深さのツリーのルート要素を除くと、その下に深さ２のツリーがある事がわかる。この部分を再帰で表現すればいけそう？？
そうしてできた処理が以下。
--combn は n要素の combinationの意 combn [] n=[] combn lst 1=map (\x -> [x]) lst combn (x:xs) n=[x:y| y <- combn xs (n-1)] ++ combn xs n main=do print $ combn [1..5] 3 -- > [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
おおエレガント！haskellで考えると無駄なく書ける。
手続き的に考えた場合
JavaScriptを使って手続き的な処理でも書いてみた。
function comb(lst, k) { var tmp = []; for(var i = 0; i < k; i++) tmp[i] = i; var res = [tmp]; while(true){ tmp = inc(tmp, lst.length-1); if(tmp) { if(uniqueness(tmp)) res.push(tmp); } else { break; } } for(var i in res) { for(var j in res[i]) res[i][j] = lst[res[i][j]]; } return res; } // [0,1,2] を受け取ると [0,1,3] を返す。値をインクリメント。 function inc(lst, max) { var res = []; for(var i = 0; i < lst.length; i++) res[i] = lst[i]; for(var i = res.length - 1; i != 0 ; i--) { if(res[i] + 1 <= max) { res[i]++; return res; } else if (i > 0){ res[i] = res[i-1] + 2; if(res[i] > max) break; } } } function uniqueness(lst) { var tmp = []; for(var i = 0; i < lst.length; i++) tmp[lst[i]] = (tmp[lst[i]] || 0) + 1; for(var j = 0; j < tmp.length; j++) if(tmp[j] > 1) return false; return true; } var ary = ["a","b","c","d","e"]; print(comb(ary,3)); // -> [["a","b","c"],["a","b","d"], ["a","b","e"], ["a","c","d"], ["a","c","e"], ["a","d","e"]]
別に無駄に長くしようとしたわけではなくて、もっとちゃんとしたアルゴリズムを使ってやれば短くできるんだろうけど。
