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

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

具体的には、いくつかの文字の組み合わせで出来た文字列を与え、各行の文字数を決めると「下の文字列はすぐ上の文字列に1文字加えたものか、1文字減らしたものしか置けない」「各文字列は一度しか使えない」というルールにしたがって文字列を並べてくれるというものです。(ルールを満たす並べ方が複数ある場合はすべて書き出し、不可能な場合はエラーを返す)
例えばa,b,c3文字の組み合わせで出来た文字列、a,b,c,ab,bc,ac,abcを与え、各行の文字数を(1,2,1,2,1,2,3)と決めると、

a
ab
b
bc
c
ac
abc

等(実際は他にもあります)の結果を書き出してくれるスクリプトです。この例は3文字で出来た7つの文字列でしたが、文字数や文字列数が増えても対応出来るものを希望します。
説明に解りにくい部分があれば質問してください。
また、以前よく似た質問をしましたのでそちらも参考にしてください。
http://q.hatena.ne.jp/1207875536
よろしくお願いします。

回答の条件
  • 1人2回まで
  • 登録:2008/09/25 08:30:24
  • 終了:2008/09/26 06:48:04

回答(2件)

id:GoldenDawn No.1

GoldenDawn回答回数426ベストアンサー獲得回数812008/09/25 19:35:49

かなり手抜き (ほとんどエラーチェックしてないので (1, 3, 1) なども通す)、

かつ力業で遅く、

しかもマルチバイト文字不可ですが。

<?php
function fact($n) {
  if ($n <= 0) return 0 ;
  for ($i = $r = 1; $i <= $n; ++$i) $r *= $i ;
  return $r ;
}

function search_patterns($strings, $lengths) {

  $result = array() ;

  $order = array_fill(0, count($lengths), 0) ;
  $patnum = fact(count($strings)) ;
  for ($i = 0; $i < $patnum; ++$i) {
    for ($n = 0, $cpat = $i; $n < count($strings); ++$n) {
      $order[$n] = $cpat == 0 ? 0 : floor($cpat / (fact(count($strings) - $n - 1))) ;
      $cpat -= $order[$n] * fact(count($strings) - $n - 1) ;
    }

    $cpat = array() ;
    $tmp = $strings ;
    for ($m = 0; $m < count($lengths); ++$m) {
      for ($n = 0; $n < $order[$m]; ++$n) array_push($tmp, array_shift($tmp)) ;
      array_push($cpat, array_shift($tmp)) ;
    }

    for ($m = 0; $m < count($cpat); ++$m) {
      if (strlen($cpat[$m]) != $lengths[$m]) break ;
      if ($m != 0 && levenshtein($cpat[$m-1], $cpat[$m]) != 1) break ;
      if ($m == count($lengths) - 1) array_push($result, $cpat) ;
    }
  }

  return $result ;
}

$s = array('a', 'b', 'c', 'ab', 'bc', 'ac', 'abc') ;
$l = array(1, 2, 1, 2, 1, 2, 3) ;

echo '<pre>' ;
$r = search_patterns($s, $l) ;
for ($i = 0; $i < count($r); ++$i) echo implode("\n", $r[$i])."\n\n" ;
echo '</pre>' ;
?>
id:youku554 No.2

youku554回答回数95ベストアンサー獲得回数02008/09/26 01:10:48

労働斡旋は法律違反

  • id:GoldenDawn
    せっかくなので UTF-8 対応。
    高速化は気が向いたら考える。


    適当なところに
    mb_internal_encoding('utf-8') ;
    を挿入


    for ($m = 0; $m < count($cpat); ++$m) {
    if (strlen($cpat[$m]) != $lengths[$m]) break ;
    if ($m != 0 && levenshtein($cpat[$m-1], $cpat[$m]) != 1) break ;
    if ($m == count($lengths) - 1) array_push($result, $cpat) ;
    }

    for ($m = 0; $m < count($cpat); ++$m) {
    if (mb_strlen($cpat[$m]) != $lengths[$m]) break ;

    if ($m != 0) {
    $pc = preg_split('//u', $cpat[$m-1], -1, PREG_SPLIT_NO_EMPTY) ;
    $cc = preg_split('//u', $cpat[$m], -1, PREG_SPLIT_NO_EMPTY) ;

    $npat = array_merge($pc, $cc) ;
    $nl = count($npat) ;
    $ul = count(array_unique($npat)) ;
    if (($nl - ($nl - $ul)*2) != 1) break ;
    }

    if ($m == count($lengths) - 1) array_push($result, $cpat) ;
    }

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

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

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

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