PHPのスクリプトを作っていただけないでしょうか。

いくつかの文字列をあるルールに従って並べて書き出すスクリプトです。
いるか賞には、少ないですが500ポイントを差し上げます。

具体的には、いくつかの文字の組み合わせで出来た文字列を与え、その中からスタートの文字列とゴールの文字列を決めると、それらの間を「下の文字列はすぐ上の文字列に1文字加えたものか、1文字減らしたものしか置けない」というルールにしたがって残りの文字列を並べて埋めてくれるというものです。(ルールを満たす並べ方が複数ある場合はすべて書き出し、不可能な場合はエラーを返す)
例えば、「い」「ろ」「は」3文字の組み合わせで出来た文字列、い,ろ,は,いろ,ろは,いは,いろは を与え、その中から「い」をスタート、「いろは」をゴールと決めると、


いろ

ろは

いは
いろは


いは

ろは

いろ
いろは

上記2種類の結果を書き出してくれるスクリプトです。この例では3つの文字で出来た7つの文字列でしたが、文字数や文字列数が増えても対応出来るスクリプトを希望します。
説明に解りにくい部分があれば質問してください。
よろしくお願いします。

回答の条件
  • 1人5回まで
  • 登録:2008/04/11 09:58:57
  • 終了:2008/04/11 20:18:22

ベストアンサー

id:JULY No.2

JULY回答回数966ベストアンサー獲得回数2472008/04/11 17:23:54

ポイント500pt

>>「すべての文字列を1回づつ使う」

対応してみました。

<?php

function get_str_sequence($start, $stop, $str_set, $charset, $max_len, $str_seq, &$result) {
    $str_seq[] = $start;

    if (strcmp($start, $stop) == 0) {
        if (count($str_seq) != count($str_set)) return;

        foreach ($str_set as $str) {
            if (array_search($str, $str_seq) === false) return;
        }

        $result[] = $str_seq;
        return;
    }

    if (strlen($start) < $max_len) {
        foreach ($charset as $char) {
            for ($i = 0; $i <= strlen($start); $i++) {
                $next_start = substr($start, 0, $i) . $char . substr($start, $i);
                if (array_search($next_start, $str_set) === false) continue;
                if (array_search($next_start, $str_seq) === false) {
                        get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
                }
            }
        }
    }

    if (strlen($start) > 1) {
        for ($i = 0; $i < strlen($start); $i++) {
            $next_start = substr($start, 0, $i) . substr($start, $i + 1);
            if (array_search($next_start, $str_set) === false) continue;
            if (array_search($next_start, $str_seq) === false) {
                get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
            }
        }
    }
}

function print_str_sequence($start, $goal, $str_list) {
    $max_str_len = 0;
    $all_char = array();

    foreach ($str_list as $str) {
        for ($i = 0; $i < strlen($str); $i++) {
            $all_char[] = substr($str, $i, 1);
        }

        if (strlen($str) > $max_str_len) {
            $max_str_len = strlen($str);
        }
    }

    $charset = array_unique($all_char);

    $result = array();
    get_str_sequence($start, $goal, $str_list, $charset, $max_str_len, "", $result);

    if (count($result) > 0) {
        foreach ($result as $sequence) {
            foreach ($sequence as $str) {
                print "$str\n";
            }
            print "\n";
        }
    } else {
        print("No sequence\n");
    }
}

$str_list = array("abc", "ab", "a", "b", "bc");
print_str_sequence("a", "abc", $str_list);
?>
id:minapoo

ありがとうございました!

こんなに早く回答していただけるとはうれしい限りです。

ワケの分からない要望に応えていただいてすみませんでした。

いるか賞500ポイントとさせていただきます!

ところで、ついうれしくて文字数&文字列数増やしてやってみたら

タイムアウトになってしまったんですが

php.iniいじったら良いんでしょうか

素人がいじらない方が良いでしょうか

2008/04/11 19:22:37

その他の回答(2件)

id:JULY No.1

JULY回答回数966ベストアンサー獲得回数2472008/04/11 15:20:39

ちゃんとデバッグした訳じゃないし、もっときれいで効率の良いコードがありそうだけど、とりあえず。

多分、文字は ASCII 限定になってると思います。

<?php
function get_str_sequence($start, $stop, $str_set, $charset, $max_len, $str_seq, &$result) {
    $str_seq[] = $start;

    if (strcmp($start, $stop) == 0) {
        $result[] = $str_seq;
        return;
    }

    if (strlen($start) < $max_len) {
        foreach ($charset as $char) {
            for ($i = 0; $i <= strlen($start); $i++) {
                $next_start = substr($start, 0, $i) . $char . substr($start, $i);
                if (array_search($next_start, $str_set) === false) continue;
                if (array_search($next_start, $str_seq) === false) {
                        get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
                }
            }
        }
    }

    if (strlen($start) > 1) {
        for ($i = 0; $i < strlen($start); $i++) {
            $next_start = substr($start, 0, $i) . substr($start, $i + 1);
            if (array_search($next_start, $str_set) === false) continue;
            if (array_search($next_start, $str_seq) === false) {
                get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
            }
        }
    }
}

function print_str_sequence($start, $goal, $str_list) {
    $max_str_len = 0;
    $all_char = array();

    foreach ($str_list as $str) {
        for ($i = 0; $i < strlen($str); $i++) {
            $all_char[] = substr($str, $i, 1);
        }

        if (strlen($str) > $max_str_len) {
            $max_str_len = strlen($str);
        }
    }

    $charset = array_unique($all_char);

    $result = array();
    get_str_sequence($start, $goal, $str_list, $charset, $max_str_len, "", $result);

    if (count($result) > 0) {
        foreach ($result as $sequence) {
            foreach ($sequence as $str) {
                print "$str\n";
            }
            print "\n";
        }
    } else {
        print("No sequence\n");
    }
}

$str_list = array("abc", "ab", "a", "b", "bc");
print_str_sequence("a", "abc", $str_list);
?>
id:minapoo

さっそくありがとうございます。

それで、まずお詫びしなければいけないのですが、上の質問文中に「すべての文字列を1回づつ使う」という条件が抜けておりました。

JULY様のお答えを確認させていただきましたら「a ab abc」というのも答えとして表示されましたので、そこを変えていただくと申し分ないと思うのです。

本当にすみません、私の説明不足でしたm(_"_)m

2008/04/11 16:14:26
id:JULY No.2

JULY回答回数966ベストアンサー獲得回数2472008/04/11 17:23:54ここでベストアンサー

ポイント500pt

>>「すべての文字列を1回づつ使う」

対応してみました。

<?php

function get_str_sequence($start, $stop, $str_set, $charset, $max_len, $str_seq, &$result) {
    $str_seq[] = $start;

    if (strcmp($start, $stop) == 0) {
        if (count($str_seq) != count($str_set)) return;

        foreach ($str_set as $str) {
            if (array_search($str, $str_seq) === false) return;
        }

        $result[] = $str_seq;
        return;
    }

    if (strlen($start) < $max_len) {
        foreach ($charset as $char) {
            for ($i = 0; $i <= strlen($start); $i++) {
                $next_start = substr($start, 0, $i) . $char . substr($start, $i);
                if (array_search($next_start, $str_set) === false) continue;
                if (array_search($next_start, $str_seq) === false) {
                        get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
                }
            }
        }
    }

    if (strlen($start) > 1) {
        for ($i = 0; $i < strlen($start); $i++) {
            $next_start = substr($start, 0, $i) . substr($start, $i + 1);
            if (array_search($next_start, $str_set) === false) continue;
            if (array_search($next_start, $str_seq) === false) {
                get_str_sequence($next_start, $stop, $str_set, $charset, $max_len, $str_seq, $result);
            }
        }
    }
}

function print_str_sequence($start, $goal, $str_list) {
    $max_str_len = 0;
    $all_char = array();

    foreach ($str_list as $str) {
        for ($i = 0; $i < strlen($str); $i++) {
            $all_char[] = substr($str, $i, 1);
        }

        if (strlen($str) > $max_str_len) {
            $max_str_len = strlen($str);
        }
    }

    $charset = array_unique($all_char);

    $result = array();
    get_str_sequence($start, $goal, $str_list, $charset, $max_str_len, "", $result);

    if (count($result) > 0) {
        foreach ($result as $sequence) {
            foreach ($sequence as $str) {
                print "$str\n";
            }
            print "\n";
        }
    } else {
        print("No sequence\n");
    }
}

$str_list = array("abc", "ab", "a", "b", "bc");
print_str_sequence("a", "abc", $str_list);
?>
id:minapoo

ありがとうございました!

こんなに早く回答していただけるとはうれしい限りです。

ワケの分からない要望に応えていただいてすみませんでした。

いるか賞500ポイントとさせていただきます!

ところで、ついうれしくて文字数&文字列数増やしてやってみたら

タイムアウトになってしまったんですが

php.iniいじったら良いんでしょうか

素人がいじらない方が良いでしょうか

2008/04/11 19:22:37
id:KeyKey No.3

KeyKey回答回数29ベストアンサー獲得回数42008/04/11 19:31:26

ポイント500pt

時間ないのでかなり汚いソースですがこんな感じでどうでしょう?

$now 現在の項目

$max ゴール

$map 全ての項目

$flg 使った項目

$ary 今まで辿った項目

$str_ary 文字列の配列

<?php
$str = "abc";
$str_ary = array();
$str_ary = str_split($str);

$len = count($str_ary);

$bin = '';
for ($i = 0; $i < $len; $i++) {
    $bin .= '1';
}

for ($i = 1; $i <= bindec($bin); $i++) {
    $map[] = str_split(sprintf("%0{$len}b", $i));
}

strSeek($map[0], $map[bindec($bin)-1], $map, array(0), array($map[0]), $str_ary);

exit;

function strSeek($now, $max, $map, $flg=array(), $ary, $str_ary)
{
    if (count($ary) === count($map) && $now === $max) {
        foreach ($ary as $key => $val) {
            foreach ($val as $key2 => $val2) {
                if ($val2 == 1) {
                    echo $str_ary[$key2];
                }
            }
            echo "<br>";
        }
        echo "-------<br>";
    }
    
    for ($i = 0; $i < count($map); $i++) {
        $exit = 0;
        foreach ($flg as $val) {
            if ($i === $val) {
                $exit = 1;
            }
        }
        if ($exit !== 1) {
            $diff = 0;
            for ($j = 0; $j < count($map[$i]); $j++) {
                if ($now[$j] !== $map[$i][$j]) {
                    $diff++;
                }
            }
            if ($diff === 1) {
                $ary2 = array();
                $ary2 = $ary;
                array_push($ary2, $map[$i]);
                $flg2 = array();
                $flg2 = $flg;
                array_push($flg2, $i);
                strSeek($map[$i], $max, $map, $flg2, $ary2, $str_ary);
            }
        }
    }
}
?>

出力

c
bc
b
ab
a
ac
abc
-------
c
ac
a
ab
b
bc
abc
-------
  • id:tukihatu
    こんなプログラム、何に使うんだろう?ゲームとか?^^;
    >「い」「ろ」「は」3文字の組み合わせで出来た文字列、い,ろ,は,いろ,ろは,いは,いろは を与え、その中から「い」をスタート、「いろは」をゴールと決める
    ユーザの入力する項目は
    スタートの文字:い
    文字列:い,ろ,は,いろ,ろは,いは,いろは
    ゴール:いろは
    見たいな感じですか?

    文字列はすべて使わないといけないんですか?
    文字列は何回も使って良いんですか?

    とりあえずそのあたりの仕様がわからないと誰も作れないと思います。
  • id:minapoo
    >文字列はすべて使わないといけないんですか?
    >文字列は何回も使って良いんですか?

    文字列はすべてを1回づつ使うという条件です。
    すみません、説明不足でしたm(_"_)m

    >ユーザの入力する項目は
    >スタートの文字:い
    >文字列:い,ろ,は,いろ,ろは,いは,いろは
    >ゴール:いろは
    >見たいな感じですか?

    その通りでございます。
  • id:tukihatu
    JULYさん早い!御見それしました^^

    ちなみに日本語対応させるならすべてのstrlenとsubstrをmb_strlenとmb_substrにすればいけます。

    formにするなら
    <p>スタート文字:
    <input type="text" name="strstart" id="strstart" />
    <br />
    使う文字列:
    <input type="text" name="strstreet" id="strstreet" />
    <br />
    ゴール:
    <input type="text" name="strend" id="strend" />
    </p>
    <p>
    <input type="hidden" name="pos" value="1" />
    <input type="submit" name="Submit" value="送信" />
    </p>
    </form>

    <?
    if($_POST["pos"] == "1"){
    $str_list = explode(",", $_POST["strstreet"]);
    print_str_sequence($_POST['strstart'], $_POST['strend'], $str_list);
    }
    ?>
    という感じでいけると思います。
    参考までに
  • id:minapoo
    ありがとうございます!
    参考にさせていただきますです。
  • id:minapoo
    KeyKeyさん、コメント付けずに終了してしまってすみませんでした。
    文字入れると組み合わせもやってくれちゃうんですね。
    すごいです。
    500ポイント差し上げますです。
    いるか賞は早い者勝ちってことでごめんなさい。
    皆様ありがとうございました。
  • id:JULY
    パフォーマンスはたぶん悪いと思います。
    馬鹿正直に再帰呼び出しで、呼び出されるたびに配列がコピーされるし。

    まぁ、プログラム的には、文字数の制限とかは無いけど、ちょっと文字数が
    増えると、調べる必要があるパターン数が爆発的に増えるので、あっという
    間に限界が来ちゃうでしょう。

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

トラックバック

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

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

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