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

2008/1/8 00:00

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

**制約条件**

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

最初、ここやここを読んで、どうやってロジック組むかと考えたのですが、前回投稿した『あみだくじ』を組んだ際、ソートすれば良い事に気づきました。

kotlin.Unit パラメータで渡されるリストの先頭から隣り合う要素同士を比較し、その大小によって要素を入れ替え、これをリスト末端まで試行します。要素入れ替えの発生はあみだくじの横棒になります。これを1ステップとして記録し、ソートが完了するまで繰り返します。

このソート方法はバブルソートに似ていますが、バブルソートと異なる点は、入れ替えが発生した要素は、そのステップ内ではもう動かしてはいけないという点です。

ソートが完了したら、記録したソート過程（ステップ）を逆順とし、これをあみだくじのパターンとします。

以下、投稿したコード。選択した言語はPHP。パラメータとして渡すリストは文字列型にする必要があります。また、お題では数字のリストという事ですが、英数字に対応した関数となっています。

<?php  
function CreateAmida($org)  
{  
    if (!ctype_alnum($org) ||  
        count(array_unique(str_split($org))) != count(str_split($org))) {  
        return NULL;  
    }  
    $bridge_num = strlen($org)-1;  
    $p = $org;  
    $step = array();  
    while (1) {  
        $chg = FALSE;  
        $step_buf = array_fill(0, $bridge_num, ‘ ‘);  
        for ($i = 0; $i < $bridge_num; $i++) {  
            if ($p[$i] > $p[$i+1]) {  
                $sub = array($p[$i]=>$p[$i+1], $p[$i+1]=>$p[$i]);  
                $p = strtr($p, $sub);  
                $step_buf[$i] = ‘-‘;  
                $i++;  
                $chg = TRUE;  
            }  
        }  
        if ($chg) {  
            $step[] = ‘|’.implode(‘|’, $step_buf).’|’;  
        } else {  
            break;  
        }  
    }  
    $res = implode(‘ ‘, str_split($p)).”\n”;  
    $res .= implode(“\n”, array_reverse($step)).”\n”;  
    $res .= implode(‘ ‘, str_split($org)).”\n”;  
    return $res;  
}  
?>