ちょうど良さそうな問題があったので、かなーり久々に Haskell してみる。
ある金額になるコインの組み合わせ数とその組み合わせを全て答え下さい。
条件）
・コインの種類は自由に設定できるようにする。
・順序が違うだけのものは一つの組み合わせとする。
（例：16の組み合わせで、[1, 5, 10]と[10, 5, 1]は同じ）
例）
コインの種類：1, 5, 10, 50, 100, 500
金額：10
組み合わせ数：4
組み合わせ：
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 5]
[5, 5]
[10]
お題：ある金額になるコインの組み合わせ - No Programming, No Life
import List (sort) solveCoin :: Integer -> [Integer] -> [[Integer]] solveCoin total coins = let coins' = reverse $ sort coins in takeCoins coins' [] total takeCoins :: [Integer] -> [Integer] -> Integer -> [[Integer]] takeCoins [] _ _ = [] takeCoins cs xs rest = let c = head cs cs' = tail cs possibleCombinations = case signum (rest - c) of -1 -> [] 0 -> [c:xs] 1 -> takeCoins cs (c:xs) (rest - c) in possibleCombinations ++ (takeCoins cs' xs rest) main = print $ solveCoin 10 [1, 5, 10, 50, 100, 500]
↓実行結果。
10],[5,5],[1,1,1,1,1,5],[1,1,1,1,1,1,1,1,1,1?
http://codepad.org/9cDnkcPt
「コインの組み合わせ数」と「その組み合わせを全て」を答えないといけないんだけど、「コインの組み合わせ数」は出力省略してる。
もっと簡単になるのかもしれないけど僕の実力ではここまでだった。あとは () じゃなくて $ を使うぐらいしか思いつかない。
bubbleSort :: Ord a => [a] -> [a] bubbleSort = bubbleSortBy compare bubbleSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] bubbleSortBy _ [] = [] bubbleSortBy cmp xs = y : (bubbleSortBy cmp (reverse ys)) where (ys, y) = bubbleBy cmp xs bubbleBy :: Ord a => (a -> a -> Ordering) -> [a] -> ([a], a) bubbleBy _ [x] = ([], x) bubbleBy cmp (x:xs@(x':xs')) = if cmp x x' == GT then let (ys, y) = bubbleBy cmp xs in (x:ys, y) else let (ys, y) = bubbleBy cmp (x:xs') in (x':ys, y) main = print $ bubbleSort [4,5,6,3,1,3,2,5,8,4,3,2]
よく見るバブルソートとちょっと違って、バブルして最後に残るやつが最大値ではなく最小値になっている。
ググってもあまりよさそうなのがなかった。
↑の bubbleBy はこれでもいい。ちょっとは分かりやすいか。
bubbleBy _ [x] = ([], x) bubbleBy cmp (x:xs) = foldl takeSmall ([], x) xs where takeSmall (ys, y) z = if cmp y z == GT then (y:ys, z) else (z:ys, y)
foldl じゃなくて foldr にしたら reverse が要らなくなるな。しかし大きなリストだと stack overflow になる可能性が。
Insertion Sort と Merge Sort をやって、次に何をやろうかなーと思って調べてたら、Shell Sort がおもしろそうだったのでやってみる。
ただし、よく見るような
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
の数列を使うものではなくて、
h(n) = 3^(n-1) -> 1, 3, 9, 27, 81, ...
でやった。
ロジックは前にやった Insertion Sort と Merge Sort (非安定版) の組み合わせなので簡単。
リストの長さが9以下のものは Insertion Sort に切り替え。
import List -- shell sort shellSort :: Ord a => [a] -> [a] shellSort = shellSortBy compare shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy _ [] = [] shellSortBy _ [x] = [x] shellSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] -- do insertion sort if list is short shellSortBy cmp xs@([x1,x2,x3]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8]) = insertionSortBy cmp xs shellSortBy cmp xs@([x1,x2,x3,x4,x5,x6,x7,x8,x9]) = insertionSortBy cmp xs -- else split into 3, shell sort each, then insertion sort the whole shellSortBy cmp xs = insertionSortBy cmp $ merge3 (shellSortBy cmp as) (shellSortBy cmp bs) (shellSortBy cmp cs) where (as,bs,cs) = split3 xs split3 :: [a] -> ([a], [a], [a]) split3 [] = ([],[],[]) split3 [x] = ([x],[],[]) split3 [x,y] = ([x],[y],[]) split3 (a:b:c:xs) = (a:as, b:bs, c:cs) where (as, bs, cs) = split3 xs merge3 :: [a] -> [a] -> [a] -> [a] merge3 [] [] [] = [] merge3 [x] [] [] = [x] merge3 [x] [y] [] = [x,y] merge3 (x:xs) (y:ys) (z:zs) = x:y:z:(merge3 xs ys zs) -- insertion sort insertionSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] insertionSortBy cmp [] = [] insertionSortBy cmp (x:xs) = insertBy cmp x $ insertionSortBy cmp xs main = print $ shellSort [23,4,5,43,6,3,2,94,3,2,63,68,95,33,22,67,4,2,67,47,89,53,26,83,56,78,96,4,32,12,45,67,45,3,68,94,21,56,7,85,3,21,6,83,24,79,34,23,32,76,54,1,24,64,98,62,19,63,28,36,18,52]
↓実行。
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
を使うにはどうしたらいいのだろう。うーん…
パターンマッチが多すぎてカッコわるいと言われたので null.drop にしてみた。
shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy _ [] = [] shellSortBy _ [x] = [x] shellSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] shellSortBy cmp xs = if null (drop 9 xs) then insertionSortBy cmp xs else insertionSortBy cmp $ merge3 (shellSortBy cmp as) (shellSortBy cmp bs) (shellSortBy cmp cs) where (as,bs,cs) = split3 xs
うちの環境ではインタープリタでもコンパイルしてもこっちのほうが速くなるっぽい。
h(n+1) = 3*h(n)+1 -> 1, 4, 13, 40, 121, ...
を使う版を作ってみた。
パフォーマンスは考えない方向で。
import List -- shell sort shellSort :: Ord a => [a] -> [a] shellSort = shellSortBy compare shellSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] shellSortBy cmp xs = insertionSortBy cmp $ shellSortBy' 4 cmp xs shellSortBy' :: Ord a => Int -> (a -> a -> Ordering) -> [a] -> [a] shellSortBy' n cmp xs = if null (drop (n*9) xs) then merge $ map (insertionSortBy cmp) $ split n xs else merge $ map (insertionSortBy cmp) $ split n $ shellSortBy' (n*3+1) cmp xs split :: Int -> [a] -> [[a]] split n xs = split' xs [] $ replicate n [] split' :: [a] -> [[a]] -> [[a]] -> [[a]] split' [] xss yss = (reverse xss) ++ yss split' xs xss [] = split' xs [] $ reverse xss split' (x:xs) xss (ys:yss) = split' xs ((x:ys):xss) yss merge :: [[a]] -> [a] merge xss = merge' [] xss merge' :: [[a]] -> [[a]] -> [a] merge' [] [] = [] merge' xss [] = merge' [] $ reverse xss merge' xss ((y:[]):yss) = y : (merge' xss yss) merge' xss ((y:ys):yss) = y : (merge' (ys:xss) yss) -- insertion sort insertionSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] insertionSortBy _ [] = [] insertionSortBy _ [x] = [x] insertionSortBy cmp [x,y] = if cmp x y == GT then [y,x] else [x,y] insertionSortBy cmp (x:xs) = insertBy cmp x $ insertionSortBy cmp xs main = print $ shellSort [23,4,5,43,6,3,2,94,3,2,63,68,95,33,22,67,4,2,67,47,89,53,26,83,56,78,96,4,32,12,45,67,45,3,68,94,21,56,7,85,3,21,6,83,24,79,34,23,32,76,54,1,24,64,98,62,19,63,28,36,18,52]
reverse しまくり、length (相当の null drop (n*9) ) しまくり。
たぶんアルゴリズム的には手続き型言語のと同じになってると思う。
import Data.List (transpose, insert) -- Insertion sort, for sorting columns. insertionSort :: Ord a => [a] -> [a] insertionSort = foldr insert [] -- Splits a list into k columns. columnize :: Int -> [a] -> [[a]] columnize k = transpose . takeWhile (not . null) . map (take k) . iterate (drop k) -- Merges columns back into a single list. decolumnize :: [[a]] -> [a] decolumnize = concat . transpose -- Each phase of the Shell sort breaks the list into k columns, sorts each with an -- insertion sort, then merges those columns back into a list. shellSortPhase :: (Ord a) => Int -> [a] -> [a] shellSortPhase k = decolumnize . map insertionSort . columnize k -- The full Shell sort, applying phases with arbitrarily large gap sizes according to -- R. Sedgewick, J. Algorithms 7 (1986), 159-173 shellSort :: (Ord a) => [a] -> [a] shellSort xs = foldr shellSortPhase xs gaps where gaps = takeWhile (< length xs) sedgewick sedgewick = concat [[9 * 2^n - 9 * 2^(n `div` 2) + 1, 8 * 2^(n+1) - 6 * 2^(n `div` 2) + 1] | n <- [0..]]
transpose を使うのは思いつかなかった。
1,11,10,27,19,53,55,117,109,233,253,489,505,977,...
という数列を使うらしい。
これと同じことをやってるらしい↓。
import Data.List shellSort xs = foldr (invColumnize (map (foldr insert []))) xs gaps where gaps = takeWhile (< length xs) $ iterate (succ.(3*)) 1 invColumnize f k = concat. transpose. f. transpose . takeWhile (not.null). unfoldr (Just. splitAt k)
もう何が何だか…
せっかく Insertion Sort をやったので、マージソートもやってみる。
mergeSort :: Ord a => [a] -> [a] mergeSort = mergeSortBy compare mergeSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] mergeSortBy _ [] = [] mergeSortBy _ [x] = [x] mergeSortBy cmp xs = mergeBy cmp (mergeSortBy cmp ys) (mergeSortBy cmp zs) where (ys,zs) = split xs split :: [a] -> ([a], [a]) split [] = ([],[]) split [x] = ([x],[]) split (x:x':xs) = (x:as, x':bs) where (as, bs) = split xs mergeBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a] mergeBy _ xs [] = xs mergeBy _ [] ys = ys mergeBy cmp xs@(x:xs') ys@(y:ys') = if cmp x y == GT then y:(mergeBy cmp xs ys') else x:(mergeBy cmp xs' ys) main = print $ mergeSort [2,3,4,5,4,3,6,3,2]
実行↓
本来の安定なマージソートなら split で前半と後半に分けないといけないところだけど、Haskell の length 演算子は O(n) なので、何度も呼びたくない。だから「とびとび」に要素を取っている。
だからこれは非安定ソート。
length を最初に一回だけ計算しておく方法だと
mergeSort :: Ord a => [a] -> [a] mergeSort = mergeSortBy compare mergeSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] mergeSortBy cmp xs = mergeSortBy' cmp xs $ length xs mergeSortBy' :: Ord a => (a -> a -> Ordering) -> [a] -> Int -> [a] mergeSortBy' _ [] _ = [] mergeSortBy' _ [x] _ = [x] mergeSortBy' cmp xs len = mergeBy cmp (mergeSortBy' cmp ys a) (mergeSortBy' cmp zs b) where (a,b) = if even len then (len `div` 2, len `div` 2) else (len `div` 2 + 1, len `div` 2) (ys, zs) = splitAt a xs mergeBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a] mergeBy _ xs [] = xs mergeBy _ [] ys = ys mergeBy cmp xs@(x:xs') ys@(y:ys') = if cmp x y == GT then y:(mergeBy cmp xs ys') else x:(mergeBy cmp xs' ys) main = print $ mergeSort [2,3,4,5,4,3,6,3,2]
のようになるはず。
実行↓
↓に載ってる splitrec というやつだと、リストの長さが分からなくても前半と後半に分けられるみたい。
どれが速いんだろうか。