【アルゴリズム】連続した数字の並びの固まりがいくつかあるとします。

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
　-- 編集距離の計算用に最初の位置を組にして記憶（ルール４の準備）
　let inputWithPos = zip input [0..]

　-- 順列で全ての候補を洗い出し（ルール３）
　let candidates = permutations inputWithPos

　-- 先頭と末尾の符号が異なる候補だけを抽出（ルール１，２）
　let passedRules = filter isDifferentSign candidates

　-- ルール適合チェック
　if null passedRules
　　then putStrLn "answer = none"
　　else do
　　　-- 各候補の編集距離を計算、最小の候補を出力（ルール４）
　　　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