人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【アルゴリズム】連続した数字の並びの固まりがいくつかあるとします。
これらの固まりは、必ず以下の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)最初の並び順からできるだけ近い並び順にしたいです。

できればソースコード(言語は問いません)つきで解説していただけないでしょうか?

●質問者: サロン日焼け
●カテゴリ:コンピュータ インターネット
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● kazutanaka
●300ポイント

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

kazutanakaさんのコメント
その通りです。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ