与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - PHP
ivoryworks
#5219()
[
PHP
]
パラメータとして渡すリストは文字列型としてください(0で始まるリスト対応)。
数字のみでなく英字も受け付ける関数仕様になっています。
また、あみだくじの特性上、重複した文字が含まれるリストを受け付けません。
リストをソート（変則的なバブルソート）する過程を記録し、過程を逆転させたものをあみだくじのパターンとするロジックです。
ex)
echo '<pre>'.CreateAmida('9876543210').'</pre>';
数字のみでなく英字も受け付ける関数仕様になっています。
また、あみだくじの特性上、重複した文字が含まれるリストを受け付けません。
リストをソート（変則的なバブルソート）する過程を記録し、過程を逆転させたものをあみだくじのパターンとするロジックです。
ex)
echo '<pre>'.CreateAmida('9876543210').'</pre>';
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | <?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;
}
?>
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]