質問: 【アルゴリズム】連続した数字の並びの固まりがいくつかあるとします。 これらの固まりは、必ず以下の4種類のうちのどれかに分類できます。 奇数で始まり、偶数個の数字 【例】 1,2,3,4 (【奇,偶】と呼ぶ) 奇数で始まり、奇数個の数字 【例】 1,2,3,4,5 (【奇,奇】と呼ぶ) 偶数で始まり、奇数個の数字 【例】 2,3,4,5,6 (【偶,奇】と呼ぶ) 偶数で始まり、偶数個の数字 【例】 2,3,4,5 (【偶,偶】と呼ぶ) これらの固まりは最初はランダムな順に並んでいます。 【例】 [1,2,3,4][2,3,4,5,6][2,3,4,5][1,2,3,4,5]...... いま、これらの固まりが10個前後あるとして、固まりを順番に並びかえたいと考えています。 ただし、並べ方にはルールがあり、 (1)固まりの最後が偶数で終わるときは、次の固まりの最初の数は奇数 (2)固まりの最後が奇数で終わるときは、次の固まりの最初の数は偶数 (3)1度使った固まりは、2度と使うことはできません また、 (4)最初の並び順からできるだけ近い並び順にしたいです。 できればソースコード(言語は問いません)つきで解説していただけないでしょうか?
回答: Haskellで書いてみた。 数字の並びはIntの組にした。 編集距離は元の位置からの移動距離の二乗の合計とした。 最初に初期位置を組にして憶えておけば、 後は順列生成、ルールチェック、距離計算、最小値選択と並べるだけ。 > module Main where > > import Data.List (all, permutations, minimumBy) > > input :: [(Int, Int)] > input = [(1,4), (2,6), (2,5), (1,5), (5,6), (11,13)] > > isDifferentSign :: [((Int, Int), Int)] -> Bool > isDifferentSign = all odd . addTailAndHead > where addTailAndHead :: [((Int, Int), Int)] -> [Int] > addTailAndHead inputWithPos = zipWith f inputWithPos (tail inputWithPos) > f :: ((Int, Int), Int) -> ((Int, Int), Int) -> Int > f ((_, t), _) ((h, _), _) = t + h > > calcEditDistance :: [((Int, Int), Int)] -> Int > calcEditDistance inputWithPos = sum $ zipWith squareDistance (map snd inputWithPos) [0..] > where squareDistance :: Int -> Int -> Int > squareDistance n m = (n - m) ^ 2 > > main :: IO () > main = do > -- 編集距離の計算用に最初の位置を組にして記憶(ルール4の準備) > let inputWithPos = zip input [0..] > > -- 順列で全ての候補を洗い出し(ルール3) > let candidates = permutations inputWithPos > > -- 先頭と末尾の符号が異なる候補だけを抽出(ルール1,2) > let passedRules = filter isDifferentSign candidates > > -- ルール適合チェック > if null passedRules > then putStrLn "answer = none" > else do > -- 各候補の編集距離を計算、最小の候補を出力(ルール4) > let minimumEditDistanceCandidate = > minimumBy (\x y -> compare (fst x) (fst y)) $ > map (\x -> (calcEditDistance x, x)) passedRules > let editDistance = fst minimumEditDistanceCandidate > let answer = map fst $ snd minimumEditDistanceCandidate > putStrLn $ "edit distance = " ++ show editDistance > putStrLn $ "answer = " ++ show answer > >