これらの固まりは、必ず以下の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
kazutanakaさん、ありがとうございます。
2017/08/20 20:45:50プログラマではないので、(私が読んで理解できるのは、せいぜいJavascriptかVisual Basicの、さらに一部です)Haskellは全くわかりませんが、やっていることは以下のようなことでしょうか?
-------
各数値と、初期位置を組にして憶えておく
順列生成 = 全ての並び順を順列組み合わせで作っておく
ルールチェック = 並び順として不適合なものを排除しておく
距離計算 = 最初の並び順との距離を計算
最小値選択 = 最も移動距離が少ない(元の並び順に近い)ものを選ぶ
-------
よろしくお願いいたします。
その通りです。
2017/08/21 00:42:36