2026-10-09
Teams.hs
import Control.Monad (replicateM)
import Data.List (nub)
teams :: Int -> String -> [String]
teams k people = [t | t <- replicateM k people, nub t == t]
main :: IO ()
main = print (teams 2 "abc")
teams k people は、people の1文字を1人として、k 人のチームをすべて、同じ顔ぶれは1回ずつ返すつもりの関数です。main は teams 2 "abc" を出力するので、引数も標準入力も使いません。いまは ["ab","ac","ba","bc","ca","cb"] が出ますが、本来は ["ab","ac","bc"] が出るはずです。
Answer
Wrong
teams k people = [t | t <- replicateM k people, nub t == t]
replicateM 2 "abc" は、"abc" から1文字選ぶことを2回繰り返した直積で、"aa" から "cc" までの9通りを並べます。直積では1人目と2人目が区別されるので、同じ人を2回選んだ "aa" も、選んだ順だけが違う "ab" と "ba" も、別々の要素です。
nub t == t で落ちるのは、1つの並びの中に同じ人が2回いる "aa"、"bb"、"cc" だけです。"ab" と "ba" はどちらも中に重複がないので両方残り、同じチームが並び順違いで2回ずつ出てきます。k 人なら、同じ顔ぶれが k の階乗の回数ずつ出ます。結果のリスト全体に nub をかけても、"ab" と "ba" は違う文字列なので消えません。
Right
teams k people = [t | t <- replicateM k people, and (zipWith (<) t (drop 1 t))]
チームは顔ぶれだけで決まるので、同じ顔ぶれの並びの中から代表を1つだけ選びます。zipWith (<) t (drop 1 t) は隣り合う2人を比べた結果のリストで、and で全部が真のもの、つまり厳密に増えていく並びだけが残ります。1つの顔ぶれを厳密に増える順に並べる方法は1通りしかないので、各チームはちょうど1回現れます。厳密に増える並びには同じ人が2回入れないので、nub の条件も要らなくなります1。
Data.Listのsubsequencesで部分列をすべて作り、長さがkのものだけを残しても、同じチームの一覧が得られます。