Hatena::Grouphaskell

Haskellで遊ぶよ

2011-08-20

Haskell で「ある金額になるコインの組み合わせ」

07:13

ちょうど良さそうな問題があったので、かなーり久々に 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

「コインの組み合わせ数」と「その組み合わせを全て」を答えないといけないんだけど、「コインの組み合わせ数」は出力省略してる。

もっと簡単になるのかもしれないけど僕の実力ではここまでだった。あとは () じゃなくて $ を使うぐらいしか思いつかない。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20110820

2010-02-15

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20100215

2009-12-08

Bubble Sort

03:59

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 になる可能性が。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20091208

2009-12-04

Shell Sort (?)

01:23

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 を使えばよかったかも

パターンマッチが多すぎてカッコわるいと言われたので 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)

もう何が何だか…

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20091204

2009-12-02

Merge Sort

05:47

せっかく 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 というやつだと、リストの長さが分からなくても前半と後半に分けられるみたい。

どれが速いんだろうか。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20091202