【アルゴリズム】連続した数字の並びの固まりがいくつかあるとします。
これらの固まりは、必ず以下の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度と使うことはできません
また、
（４）最初の並び順からできるだけ近い並び順にしたいです。
できればソースコード（言語は問いません）つきで解説していただけないでしょうか？
みんなの回答
-
kazutanaka
満足300pt
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 -
kazutanakaこの質問へのコメント
質問の情報
- 登録日時
- 2017-08-16 21:21:39
- 終了日時
- 2017-08-23 21:25:05
- 回答条件
- 1人3回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
この英文どうなってますか？ The boy seemed to be waiting for his mother to come.（その少年は母親が来…
匿名質問者
3
1
-
不定詞の形容詞的用法らしいんですけど、副詞的用法と書いたら✖️ですか？ I want to buy a book to read …匿名質問者11
-
日向陽葵という○V女優が好きなのですが似ている○V女優はいますか匿名質問者
-
共通テストで使われるプログラミング言語は共通テスト特有の言語と聞いたのですが、受験勉強で身につけたプ…匿名質問者21
-
内定してほしいポケモンはいますか？匿名質問者
つまり、１，４，５（奇数・奇数）という固まりは存在しない。
であれば、奇数＋偶数－１＝遇数、偶数＋偶数または奇数＋奇数は１差し引くと奇数、なので括弧内の２つの数から終わりの数がまず判定できる。
で、始まり偶数、終わり偶数、始まり奇数、終わり偶数をそれぞれ４つの変数にカウントする。
始まり偶数と終わり奇数がイコールでなくプラマイ１であるときは多い方を端部に置く。
プラマイ２以上差があるときは全部ならびきらないからやめる。
みたいなことで成否判定しながらソートみたいにすればいいとおもいまーす。
整数の公差１の等差数列＞その通りです。
書き方がわかりにくくてすみません。
ちなみに、
＞始まり偶数と終わり奇数がイコールでなくプラマイ１であるときは多い方を端部に置く
とは、どういう条件と操作を指しているのでしょうか？
そうしたケースに陥った際には処理が継続できなくなりますので、
無駄な処理をする前にエラー終了してしまおうというのが続く
> プラマイ２以上差があるときは全部ならびきらないからやめる。
という部分。
そして、たとえば最初の配列が偶数スタートだった場合に、
先頭の数値が偶数のデータが１つ余っただけでもやはり処理を中断せざるをえないわけですが、
このケースは奇数スタートに変更すれば全データを規則どおりに並べきるため、
そうしたケースをエラー終了させずに救済するのが
> 始まり偶数と終わり奇数がイコールでなくプラマイ１であるときは多い方を端部に置く
という処理ですね。
【偶、奇】→［（最初の数が）偶、（最後の数も）偶］のように別のマトリックスというか属性値におきかえます。
【偶、偶】→[偶、奇]
【奇、偶】→[奇、偶]
【奇、奇】→[？、？] （自分であてはめて考えて）
てなぐあいにおきかえちゃいます。４つのグループに属する「固まり」の個数はこの操作ではかわりません。
目標は
操作１０
１０コの固まりをいれかえてうまくつなげます。
ですがその前、おそらく操作２に成否判断を入れたらいいですねということ。必ず１０コの固まりが並ぶように出来ているかどうかを見ます。
操作２
[]×４グループには始まりの偶か奇が合計１０コくらい、また終わりの偶数か奇が合計１０コくらいそれぞれ存在するわけですがの「始まりの偶」と「終わりの奇」がイコール、かつ「始まりの奇」と「終わりの偶数」なら成功するから操作８に進む。
操作３
操作２の条件にあてはまらないけれど、どちらもプラマイ１のものなら、「多いもの」を開始か終了におけば成功する。始まりの奇が終わりの偶より１つ多いときは、始まりの奇を含む固まりを冒頭におけば、だれともつながらなくてよいラッキーチャンスかもしれない。（この操作３で可能と判定されてもあとで不能判定にくつがえる場合もあります）
操作４
操作３の条件にもあてはまらず、プラマイ２以上差が開くときは、１０コすべてつかってつながる列をつくることはできない。必ず８コくらいならべかえたとこでやめることになる。
【偶,偶】＝{0,0} ⇒ 次は偶数スタート{0,x}
【偶,奇】＝{0,1} ⇒ 次は奇数スタート{1,x}
【奇,偶】＝{1,0} ⇒ 次は奇数スタート{1,x}
【奇,奇】＝{1,1} ⇒ 次は偶数スタート{0,x}
次に必要となるデータが奇数スタートなのか偶数スタートなのかは
排他的論理和でそのまま求められます。
たぶん気づいているとは思うのですけれども一応念のため。
椶櫚さん、なぽりんさん、コメントありがとうございます。
全てつなげることができない=エラー終了するケースがあるのはわかっていました。
偶奇を、01のビットで表し、排他的論理和を取るところも、素晴らしいです。
ですが、理解力が足りないのか、
＞成功するから操作８に進む。
＞だれともつながらなくてよいラッキーチャンス
のところがよく分かりません。
また、ソートする際の手法についてはどうでしょう？
この程度の数なら、全通り試すのか、
枝刈り？ メモ化再帰？（よく分かっていません）などを使うのでしょうか？
図々しいようですが、よろしくお願いします。
なぽりんはプログラマとかじゃないからようしらんけどね。
1.【偶,奇】 （次は奇数スタート
2.【奇,偶】 （次は奇数スタート
3.【偶,？】
というような状態にあるとすると、
全てのデータをきちんと並べきる事を確認済みである以上、
4番目以降に【奇、奇】というデータが必ず存在するはずですので、
それを探して2番目と入れ替えれば済むのかなと思います（基本的には）。
なぜ基本的にはなのかというと、【奇、奇】が複数存在した場合に、
先に見つけた方を機械的に入れ替えてしまうと
> （４）最初の並び順からできるだけ近い並び順にしたいです。
の条件から外れてしまうような気がするためです。つまり、
1.【偶,奇】 （次は奇数スタート
2.【奇,偶】 （次は奇数スタート
3.【偶,？】
4.
5.
6.【奇、奇】 （次は偶数スタート
7.【偶,？】
8.
9.
10.【奇、奇】 （次は偶数スタート
11.【奇,？】
このような場合、
2と6を入れ替えてしまうと元々正常だった6と7の整合性が崩れてしまうので、
2と10を入れ替えるのが正解になるのかなぁと。
# もしかするとなぽりんさんやkazutanakaさんとは解釈が異なるかもしれませんが、
# 私は（４）の内容をこう受け止めました。