>Ruby 初心者スレにあった問題を、なんとなく Haskell で解いてみる。
>
>
>a,b,cと３（n)個の要素があった時に、全通りの組み合わせを出力するにはどんなやり方が賢いですか？a-b-cとc-b-aは区別しますし、a-a-aや、a-aも出力したいです。nは最大でも10程度なので、簡単なアルゴリズムで良いと思うのですが。
>
>
>基本は、まあ、こうなるだろうか。
>
>repPerm :: Int -> [a] -> [[a]]
repPerm 0 _ = [[]]
repPerm n [] = []
repPerm n l@[x] = map (replicate n) l
repPerm n (x:xs) = concatMap f [0..n]
where f i = map (replicate i x ++) $ repPerm (n-i) xs
>
>さいしょ、 n = 0 のときをうっかり
>
>concatMap (flip repPerm l) [1..length l]
>
>とでもすれば良いだろう。
>
>動作をテストしてみる。
>
>*Main> map (List.intersperse '-') $ (\l -> concatMap (flip repPerm l) [1..length l]) "abc"
["c","b","a","c-c","b-c","b-b","a-c","a-b","a-a","c-c-c","b-c-c","b-b-c","b-b-b","a-c-c","a-b-c","a-b-b","a-a-c","a-a-b","a-a-a"]
>
>なんか順序が逆順ぽい雰囲気なのが気になるが、まあよかろう(どうしても気になるなら
>
>ついでに、繰返し数に上限を与えるのを考えてみた。トランプみたいな感じ。するとこうなるかな。
>
>repPerm' :: Int -> Int -> [a] -> [[a]]
repPerm' 0 _ _ = [[]]
repPerm' n _ [] = []
repPerm' n s l@[x] | n <= s = map (replicate n) l
| otherwise = []
repPerm' n s (x:xs) = concatMap f [0..min n s]
where f i = map (replicate i x ++) $ repPerm' (n-i) s xs
>
>こちらも最初、 min n s を s にしてしまい、結果リストがどんどん長くなってたいへん困った。
>
>ではちょっと計算させてみよう。
>
>*Main> length $ repPerm' 10 4 [1..13]
566280
>
>てことで、トランプで10枚をめくるときのバリエーションは56万通りくらいあるらしい。
>
>と言われると「なるほど」と思う人もいるかもしれないけれど、これは実はスートを見てないんで何通りか、というのにはあんまり意味がない。大貧民とかのゲームならカードの数値だけで良いんでいいだろうけれど(って思ったけど「階段」とかスートが同じ必要のあるルールはいくつかあるのでやっぱりだめだ)。で、スートを考慮するならふつうに52種類のカードで
>permutation
> combination を計算した方がよく、その場合はもっとバリエーションは増える。
>
>注: permutation だと順序に違いが出てしまうから、ふつうは組合せですな。とほほ。
>
>さらに注: もとの題意は combination じゃなくて permutation だから、答えになってないことにあとで気付きました。とほほ。まあ、これはこれで残しますが、どうするかな。
>
