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

これらの固まりは、必ず以下の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人3回まで
  • 13歳以上
  • 登録:2017/08/16 21:21:39
  • 終了:2017/08/23 21:25:05

回答(1件)

id:kazutanaka No.1

kazutanaka回答回数4ベストアンサー獲得回数12017/08/19 12:10:59

ポイント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
 -- 編集距離の計算用に最初の位置を組にして記憶(ルール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

id:salon_hiyake

kazutanakaさん、ありがとうございます。

プログラマではないので、(私が読んで理解できるのは、せいぜいJavascriptかVisual Basicの、さらに一部です)Haskellは全くわかりませんが、やっていることは以下のようなことでしょうか?
-------
各数値と、初期位置を組にして憶えておく

順列生成 = 全ての並び順を順列組み合わせで作っておく

ルールチェック = 並び順として不適合なものを排除しておく

距離計算 = 最初の並び順との距離を計算

最小値選択 = 最も移動距離が少ない(元の並び順に近い)ものを選ぶ
-------

よろしくお願いいたします。

2017/08/20 20:45:50
id:kazutanaka

その通りです。

2017/08/21 00:42:36
  • id:NAPORIN
    「連続した固まりの並び」というのは、整数の公差1の等差数列(要素数は有限)ということですかね。
    つまり、1,4,5(奇数・奇数)という固まりは存在しない。
    であれば、奇数+偶数-1=遇数、偶数+偶数または奇数+奇数は1差し引くと奇数、なので括弧内の2つの数から終わりの数がまず判定できる。
    で、始まり偶数、終わり偶数、始まり奇数、終わり偶数をそれぞれ4つの変数にカウントする。
    始まり偶数と終わり奇数がイコールでなくプラマイ1であるときは多い方を端部に置く。
    プラマイ2以上差があるときは全部ならびきらないからやめる。
    みたいなことで成否判定しながらソートみたいにすればいいとおもいまーす。
  • id:salon_hiyake
    なぽりんさん、コメントありがとうございます。

    整数の公差1の等差数列>その通りです。

    書き方がわかりにくくてすみません。

    ちなみに、
    >始まり偶数と終わり奇数がイコールでなくプラマイ1であるときは多い方を端部に置く

    とは、どういう条件と操作を指しているのでしょうか?
  • id:jwrekitan
    データに偏りがある場合の例外処理がどこにも指定されていませんから、
    そうしたケースに陥った際には処理が継続できなくなりますので、
    無駄な処理をする前にエラー終了してしまおうというのが続く

    > プラマイ2以上差があるときは全部ならびきらないからやめる。

    という部分。
    そして、たとえば最初の配列が偶数スタートだった場合に、
    先頭の数値が偶数のデータが1つ余っただけでもやはり処理を中断せざるをえないわけですが、
    このケースは奇数スタートに変更すれば全データを規則どおりに並べきるため、
    そうしたケースをエラー終了させずに救済するのが

    > 始まり偶数と終わり奇数がイコールでなくプラマイ1であるときは多い方を端部に置く

    という処理ですね。
  • id:NAPORIN
    操作1

    【偶、奇】→[(最初の数が)偶、(最後の数も)偶]のように別のマトリックスというか属性値におきかえます。
    【偶、偶】→[偶、奇]
    【奇、偶】→[奇、偶]
    【奇、奇】→[?、?] (自分であてはめて考えて)
    てなぐあいにおきかえちゃいます。4つのグループに属する「固まり」の個数はこの操作ではかわりません。
     
    目標は
    操作10
    10コの固まりをいれかえてうまくつなげます。
     
    ですがその前、おそらく操作2に成否判断を入れたらいいですねということ。必ず10コの固まりが並ぶように出来ているかどうかを見ます。
      
    操作2 
    []×4グループには始まりの偶か奇が合計10コくらい、また終わりの偶数か奇が合計10コくらいそれぞれ存在するわけですがの「始まりの偶」と「終わりの奇」がイコール、かつ「始まりの奇」と「終わりの偶数」なら成功するから操作8に進む。
     
    操作3
    操作2の条件にあてはまらないけれど、どちらもプラマイ1のものなら、「多いもの」を開始か終了におけば成功する。始まりの奇が終わりの偶より1つ多いときは、始まりの奇を含む固まりを冒頭におけば、だれともつながらなくてよいラッキーチャンスかもしれない。(この操作3で可能と判定されてもあとで不能判定にくつがえる場合もあります)
     
    操作4
    操作3の条件にもあてはまらず、プラマイ2以上差が開くときは、10コすべてつかってつながる列をつくることはできない。必ず8コくらいならべかえたとこでやめることになる。
     
  • id:jwrekitan
    それから4つの分類ですが、偶を0、奇を1というフラグに見立てた場合に

    【偶,偶】={0,0} ⇒ 次は偶数スタート{0,x}
    【偶,奇】={0,1} ⇒ 次は奇数スタート{1,x}
    【奇,偶】={1,0} ⇒ 次は奇数スタート{1,x}
    【奇,奇】={1,1} ⇒ 次は偶数スタート{0,x}

    次に必要となるデータが奇数スタートなのか偶数スタートなのかは
    排他的論理和でそのまま求められます。
    たぶん気づいているとは思うのですけれども一応念のため。
  • id:NAPORIN
    椶櫚さんいつも私のわかりにくい説明の補完ありがとうございます~ ではではノシ
  • id:salon_hiyake

    椶櫚さん、なぽりんさん、コメントありがとうございます。

    全てつなげることができない=エラー終了するケースがあるのはわかっていました。
    偶奇を、01のビットで表し、排他的論理和を取るところも、素晴らしいです。
    ですが、理解力が足りないのか、

    >成功するから操作8に進む。

    >だれともつながらなくてよいラッキーチャンス

    のところがよく分かりません。

    また、ソートする際の手法についてはどうでしょう?
    この程度の数なら、全通り試すのか、
    枝刈り? メモ化再帰?(よく分かっていません)などを使うのでしょうか?
    図々しいようですが、よろしくお願いします。
  • id:NAPORIN
    操作8では古きよきバブルソートのように、「すぐに前のものとつなげられない固まりを順番で1つ後ろにずらす」「前のものと次のものをつなげてよければその次の固まりとの判定に進む」をやればいいのでは。
    なぽりんはプログラマとかじゃないからようしらんけどね。
     
  • id:NAPORIN
    「なるべくもとの順番」の「もとの順番との近さ判定基準」も自分で決めなくてはいけないんでバブルソートとはいいきれないですね。次の次のヤツと千日手になる可能性あるもんね。
  • id:jwrekitan
    ソートを開始する前の段階で例えば

    1.【偶,奇】 (次は奇数スタート
    2.【奇,偶】 (次は奇数スタート
    3.【偶,?】

    というような状態にあるとすると、
    全てのデータをきちんと並べきる事を確認済みである以上、
    4番目以降に【奇、奇】というデータが必ず存在するはずですので、
    それを探して2番目と入れ替えれば済むのかなと思います(基本的には)。
    なぜ基本的にはなのかというと、【奇、奇】が複数存在した場合に、
    先に見つけた方を機械的に入れ替えてしまうと

    > (4)最初の並び順からできるだけ近い並び順にしたいです。

    の条件から外れてしまうような気がするためです。つまり、

    1.【偶,奇】 (次は奇数スタート
    2.【奇,偶】 (次は奇数スタート
    3.【偶,?】
    4.
    5.
    6.【奇、奇】 (次は偶数スタート
    7.【偶,?】
    8.
    9.
    10.【奇、奇】 (次は偶数スタート
    11.【奇,?】

    このような場合、
    2と6を入れ替えてしまうと元々正常だった6と7の整合性が崩れてしまうので、
    2と10を入れ替えるのが正解になるのかなぁと。

    # もしかするとなぽりんさんやkazutanakaさんとは解釈が異なるかもしれませんが、
    # 私は(4)の内容をこう受け止めました。
  • id:salon_hiyake
    みなさん、ありがとうございました。実装はまだですが、大きな前進をすることができました。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません