与えられた並べ替えを実現するあみだくじの生成 in diff DouKaku?

与えられた並べ替えを実現するあみだくじの生成

お題#4476を見て思いつきました。

0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。

与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：

 0 1 2 3 4 5
 | | |-| |-|
 | |-| |-| |
 |-| |-| | |
 | |-| |-| |
 | | |-| |-|
 | | | |-| |
 3 5 2 4 0 1

一応、制約条件を示しておきます。

あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります。
同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。

一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。

post comment

Posted feedbacks - diff

(5 4 3 2 1 0)でテストしたところ、正しく解を見つけないバグがあったので、修正します。

プラス評価いただいていたのに申し訳ないです。

コメント元の投稿は自分でマイナスしておきました。

--- dk109.bug.ml        2007-12-17 23:28:16.000000000 +0900
+++ dk109.ml    2007-12-17 23:28:55.000000000 +0900
@@ -38 +38 @@
-        let costcomp (c1, c2) (m1, m2) = c1 >= m1 ||  c2 >= m2 in
+        let costcomp (c1, c2) (m1, m2) = c1 > m1 ||  c2 > m2 in
@@ -57 +57 @@
-    let best, (c,d) = solve target (comb len) (len, len * len) start in
+    let best, (c,d) = solve target (comb len) (len+1, len * len) start in

DouKaku?

与えられた並べ替えを実現するあみだくじの生成

Posted feedbacks - diff

Index

Feed

Other

Link

Pathtraq