総当たりのアルゴリズムについて

質問

このジャンルでお願いします。
例えば、「aba」という文字列なら、
a
b
ab
aa
aba
という要素（順不同です）を得たいと思い、自分なりに作ってみたのですが、
やはり調べる文字数が9文字辺りから処理に時間がかかり重くなってしまいます・・・
もちろんこういうアルゴリズムではそうなることはしょうがないと思いますが、
もう少し効率の良いやり方があればアドバイスをい頂けないでしょうか？
下に自分作った例です（メソッド名とか滅茶苦茶ですが・・^^;））

//文字の総当たりを得る
//aba なら a,b,ab,aa,aba
class AllCombinationCharacter
{
private $_characters = array();
public function __construct($text)
{
$this->_characters = self::split($text);
}

public static function split($text)
{
$cnt = 0;
$arr = array();
while ($chara = substr($text, $cnt++, 1)) {
$arr[] = $chara;
}
return $arr;
}

private function setList(&$list, $addText)
{
if (is_array($list)) {
$find = false;
foreach ($list as $item) {
if (self::isMatchInRandomOrder($item, $addText)) {
$find = true;
break;
}
}
if (!$find) {
$list[] = $addText;
}
}
}

private function recursive($list, $addText, $startIndex)
{
for ($i = $startIndex; $i < count($this->_characters); $i++)
{
$text = "";
$text .= $addText . $this->_characters[$i];
//echo "t=" . $text . "<br>\n";
$this->setList(&$list, $text);
$this->recursive(&$list, $text, $i + 1);
}
}

public function getList()
{
$list = array();
$this->recursive(&$list, "", 0);
return $list;
}

// 順不同の文字列マッチ
// "aba" と　”aab”は一緒(true)
public static function isMatchInRandomOrder($text1, $text2)
{
$tips = self::split($text2);
for ($i = 0; $i < count($tips); $i++) {
$searchString = $tips[$i];

$text1 = preg_replace("/{$searchString}/", "", $text1, 1);

if ($text1 == "")
{
break;
}
}

if ($text1 == "" && $i == count($tips) - 1)
{
return true;
}
return false;
}
}

$obj = new AllCombinationCharacter("abaaxyz");
foreach ($obj->getList() as $item) {
echo "t=" . $item . "<br>\n";
}

回答No.4

bm_hiro · ベストアンサー

正直、俺は classを 分ってません。なので、そちらのソースも読めてません。
更に言うと正規表現も理解してませんし、習得できているフレームワークも1個もありません。
メンバ変数って何？状態だったりもします。

さて、いきなり関係ない話題から入ってしまいましたが、家に帰ってきてみて、見たら ソートするの忘れてたり、変数 被って使ったりしてたので、修正＆説明追加。

<?php
$str = "ababcdefgh";

/* 文字列の数をカウント(↓↓で配列にしたものをcount()しても良かったけど) */
$length = strlen($str);
/* 文字列を配列に分ける */
$DimStr = str_split($str);
/* 上の配列をソート（←忘れてたのコレ） */
sort($DimStr);

/* 何回ループさせるか */
$loop = pow(2 , $length);
/* ↑なんで 2の累乗にしてるかってのは 二進数で総当りをするから。 */
for($i=1;$i<$loop;$i++) {
/* 10進数を二進数に変換（↓変数被ってたのコレ $strだった） */
$bin = decbin($i);
/* 左を0で埋めて 桁を揃える。 */
$mask = sprintf("%0{$length}d" , $bin);
/* これも 配列に 分解。 */
$DimMask = str_split($mask);
$ans = "";
/* 桁数分 繰り返し。 */
foreach($DimMask as $j => $bit) {
/* 1に なっている時だけ 文字列の 該当箇所の 文字を くっつける。 */
$ans .= ($bit == 1) ? $DimStr[$j] : "";
}
/* 出来上がったものを 配列のキーとして入れる。ついでに、既に同じものがあった時はカウントアップ。 */
$DimAnswer[$ans]++;
}

print_r($DimAnswer);
?>

お礼

ご回答ありがとうございます。
なるほど、試してみました凄い速度があがりました。
ありがとうございます。
ただ取得できる値は、自分が求めている結果通りなのですが、
どうも文字列が
$str = "abcdefghijkl";
12桁だと対応してないようなのです・・・
で原因を自分なりに調べてみたら
$mask = sprintf("%0{$length}d" , $bin);
の%dがどうやら原因らしいのです。
例えばこのやり方で調べてみると

$loop = pow(2 , 12);
$str = decbin($loop);
$mask = sprintf("%0{$length}d" , $str);
print "str=" . $str . " m=" . $mask . "<br>\n";//str=1000000000000 m=2147483647

と2147483647の値以上は扱えないらしいのです。
一応windows7の64ビットでXAMPPの環境でやっているのですが、
どうしたら%dの扱える範囲を増やすことができるのでしょうか？

回答No.7

bm_hiro

何度もすみません。

＞ $mask = sprintf("%0{$length}F" , $bin);
＞ 得られた行の数は1040行で時間は0.06秒ぐらいでした。

＞ $mask = str_repeat("0" , ($length - strlen($bin))) . $bin;
＞ 得られた行の数は4095行で時間は0.05秒ぐらいでした。

この違いが ちょっと腑に落ちなかったんで、俺も試してみました。

結論 : %F のほうは 小数点入ってしまってました。

ちなみに、%s で str_repeat と同じような結果になるようです。
マニュアルによると、「s - 引数を文字列として扱い、表現します。」
常に %d しか使ってなかったもんですから、すっかり %s の存在を忘れてました。

http://php.net/manual/ja/function.sprintf.php

あと 「4095行」って言う数字を見て とある可能性に気が付いたんですけど、これって 「2の12乗-1」ですよね。
多分、「文字列の中に 同じ文字がない12文字の文字列」だったんじゃないですか？
同じ文字がない条件においては、単純に ↑これで計算できるって事かもしれません。

なので、同じ文字の数を数えたりして「なんやかんや」すると、総当りしなくても いいのかもしれません。
「なんやかんや」に関しては ツッコまないでください。
分ってて書いてるわけでなくて、もしかしたら法則性があるのかもと ふと思っただけですので。

お礼

ご回答ありがとうございます。

＞これって 「2の12乗-1」ですよね。
なるほど、たしかにその数字ですね。。

＞「文字列の中に 同じ文字がない12文字の文字列」
そうですね、試しているうちに全て違う文字が一番時間がかかっていたようなので
自分は基本的に試すときは全て違う文字から試しています。

＞総当りしなくても いいのかもしれません。
なるほど、たしかに何か工夫できそうな気がします。。
しかしとりあえず得られた結果は満足でしたので、これで質問を終わりたいと思います。
ありがとうございました。

回答No.6

1minn

#1です

#4で求められている %dに代わるものであれば%F（小文字かも）で対応しては？
Int型では10桁が限界ですが、floatだと扱える範囲は大きくなります。

が、どっちにしろ限界はあるので、文字数が倍になれば破たんしちゃいますね。

#4にて提示されているコードで疑問に思ったのですが、「aba」を実行した場合に「aab」になりますよね？
質問には「aba」とありますが・・・
#1への返答にも同様に「abab」という値がありますが、これも「aabb」になっちゃいますよね？
実際に求められているものはこれで正しいんですか？

いまいち仕様が理解出来なくてすみません。頭悪いな・・・
あとforeachのエラー（ワーニング）は出ないですね。失礼しました。
日頃から癖で
if ( is_array($arr) && count($arr) > 0 )
ってのをチェックしてからforeachを使うようにしてます。なので要素が空だと怒られちゃうと無意識に思ってました。

お礼

ご回答ありがとうございます。

＞「aba」を実行した場合に「aab」になりますよね？
いえたしかになりましたが、自分の希望とする結果は
aabでもbaaでもabaでも文字の順番は関係なくて、
とにかく
aが2文字、
bが1文字
の合わせて3文字のユニークな行が
１つだけ得られればいいのです。

＞いまいち仕様が理解出来なくてすみません。
いえこちらこそ自分ですらはっきり理解できなくて^^;）
質問自体のミスをしたり、他の方にうまく説明できない状況です・・・

＞if ( is_array($arr) && count($arr) > 0 )
自分もたまにというか^^;）出ることがあるので、
初めはつけていたのですが、この例のコードではでなかったので
一応取り外したという経緯です。。

今、%Fで試したみたのですが、
$mask = sprintf("%0{$length}F" , $bin);
得られた行の数は1040行で時間は0.06秒ぐらいでした。

No.5のbm_hirosさんの提示して頂いたやり方では
$mask = str_repeat("0" , ($length - strlen($bin))) . $bin;
得られた行の数は4095行で時間は0.05秒ぐらいでした。

なんか不思議な^^;）結果というかおそらく行数的には後者の方が
自分が求めている結果だと思います。
それにしても行が多くなったのに秒数が少し減るというのは
自分的には不思議ですね。。。

回答No.5

bm_hiro

場当たり的な対応で申し訳ないんですけど、これでやってみてください。
桁を揃えるだけなので、sprintf() にこだわる必要はありませんので。

$mask = str_repeat("0" , ($length - strlen($bin))) . $bin;

ただ、二進数の総当りだと 桁が増えると 天文学的数字になりかねないんで、キツいかもしれないですね。(´・ω・`)

お礼

ご回答ありがとうございます。
＞ただ、二進数の総当りだと 桁が増えると 天文学的数字になりかねないんで、キツいかもしれないですね。
いやいやこれ滅茶苦茶早くないですか^^;）
12文字の$str = "abcdefghijkl";
で試したのですが、0.05秒でした^^;）
全部あるかどうかというのは多すぎて分からないのですが、
一応上から下まで見渡してa～lまで含んであったので、おそらくその通りなんでしょうね。。
自分的には12文字くらいは必要だったので助かりました。
ありがとうございます。

ちなみにいいろいと試してみたのですが、16文字から急にきつく（時間がかかる）なりました。
$str = "abcdefghijklmnop";

回答No.3

bm_hiro

今 あまり時間無いので 説明はしょりますが、つまりは こんな感じです。
何か 意図してたものと違ってたらすみません。

<?php

$str = "ababcdefgh";

$length = strlen($str);
$DimJob = str_split($str);

$loop = pow(2 , $length);

for($i=1;$i<$loop;$i++) {
$str = decbin($i);
$mask = sprintf("%0{$length}d" , $str);
$DimMask = str_split($mask);
$ans = "";
foreach($DimMask as $j => $bit) {
$ans .= ($bit == 1) ? $DimJob[$j] : "";
}
$DimAnswer[$ans]++;
}

print_r($DimAnswer);
?>

回答No.2

bm_hiro

正直、なんで こんな長いスクリプトになってるのかなー。。。と思いました。
とか言っておきながら、自分で書いてもこんな長くなるかもしれません。

面倒なので ちゃんと動くものは作りませんが、俺なら以下のような感じにします。

1.まず、与えられた文字列を ソートします。
配列にぶった切って sort()すると楽かもしれません。
マルチバイト文字はないって前提で考えてますのでご了承ください。
これは↓の対策としてソートしただけです。

// 順不同の文字列マッチ
// "aba" と　”aab”は一緒(true)

2.文字の数の分の2進数を用意します。

3.2進数でマスクかけてフラグが立ってる（1になってる）部分だけ結合していって文字列にします。

4.んで、その文字列を「配列のキー」として、格納します。こうすると自動的に重複は除外されます。要素はカウンタにするなりなんなりお好みで。

5.配列のキーが お望みの答えになってるはずです。

テキトーに考えたので、どっかでおかしな事になるかもしれませんし、処理速度とかはどうなるか分りません。
俺なら とりあえず こんな感じで試してみますかねーって程度の意見としてお聞きください。

お礼

ご回答ありがとうございます。
なるほど、たしかに連想配列なら自然と重複が出なくなりますね。
参考になりました。
ですが、
＞3.2進数でマスクかけてフラグが立ってる（1になってる）部分だけ結合していって文字列にします。
これの（1になってる）と仰ったのですが、どのようにして1にしているのでしょうか？
＞配列にぶった切って sort()すると
この部分と関係してるのかな？と思ったのですが、
これは

for ($i = $startIndex; $i < $cnt; $i++)
{
$text = "";
$text .= $addText . $this->_characters[$i];

この部分で置き換えると、$this->_flagsみたいなフィールドがあったとして
それをこのforループと全く一緒のループの仕方でフラグを1にするということなのでしょうか？
つまり自分のこのループでキーを作ってやるやり方と、bm_hiroさんが仰ってるフラグを立ててからキーを作る
やり方の大きなといったらあれですが、違いというかメリットがよく分からないのですが、
そこらへんを教えて頂けないでしょうか？

回答No.1

1minn

仮に「abab」だった場合は「ab」ってのが二つになるんでしょうか？
重複は省くかどうかで作り方も少し変わるかな・・・
「aba」と「aab」は一緒ってルールがよくわかんないです・・・
この場合は「ab」二つにはならないのかな？

というかまずエラーかワーニングでますよねこの状態だと。
初回にsetListが実行される段階だとforeachのとこで出ませんか？
（ナナメ読みな感じなので間違ってたらごめんなさい）
あと、想定外かもしれませんが、getListを実行したあとの結果も同様に。

で、ところどころ「参照」を使ってますが効率的ではないと思いました。
最終的に処理が終わった段階でreturn $listに入ってる値が欲しいんですよね？
それであれば、やたらと＆が登場して読みにくい事も含め、メンバ変数にした方がよいです。

あとループでcountを使うのはメモリ資源の無駄遣いになります。こことか。
for ($i = $startIndex; $i < count($this->_characters); $i++)

例えば
$this->_cnt = count($this->_characters);
的な事をコンストラクタでやっとけば、あとはその変数を使えばいいだけですから、count関数が実行される数は減りますよ。

こんな感じで
for ($i = $startIndex; $i < $this->_cnt; $i++)

全部はちゃんと見てないんで他にもありそうです。

お礼

ご回答ありがとうございます。

＞仮に「abab」だった場合は「ab」ってのが二つになるんでしょうか？
いえそのケースなら、
a
ab
aba
abab
abb
aa
b
bb
になります（例のコードの結果です）。
つまり「ab」というのはその得た行のユニーク値です。
ですが、No.2でbm_hirosさんも仰っていますが、
自分も同じ候補のカウント数が欲しいと思ったので
例のコードと意図が少し変わってきますが、
a　2
ab　2
abab 1
・・・
という具合で結果が得たいです（と思いました。。）

＞というかまずエラーかワーニングでますよねこの状態だと。
＞初回にsetListが実行される段階だとforeachのとこで出ませんか？
確認なのですが、これは太字（^^）のPHPエラーが出るということですよね？
それならば今のところは出てないです。。

＞それであれば、やたらと＆が登場して読みにくい事も含め、メンバ変数にした方がよいです。
＞あとループでcountを使うのはメモリ資源の無駄遣いになります。こことか。
なるほど、たしかに効率以前に見難いですよね・・・
そこで仰るように修正して文字列「abcdefgh」試してみたところ
0.62～0.65秒
から
0.57～0.59秒
になりました。
まあこれは測度がどうとかいう問題じゃないかもしれませんが
とにかく良くなったと思います。
参考になりました。

補足

すいません、補足を借ります。。。

//文字の総当たりを得る
//aba なら a,b,ab,aa,aba
class AllCombinationCharacter
{
private $_characters = array();
private $_list = array();
public function __construct($text)
{
$this->_characters = self::split($text);
}

public static function split($text)
{
$cnt = 0;
$arr = array();
while ($chara = substr($text, $cnt++, 1)) {
$arr[] = $chara;
}
return $arr;
}

private function setList($addText)
{
if (is_array($this->_list)) {
$find = false;
foreach ($this->_list as $item) {
if (self::isMatchInRandomOrder($item, $addText)) {
$find = true;
break;
}
}
if (!$find) {
$this->_list[] = $addText;
}
}
}

private function recursive($addText, $startIndex)
{
$cnt = count($this->_characters);
for ($i = $startIndex; $i < $cnt; $i++)
{
$text = "";
$text .= $addText . $this->_characters[$i];
//echo "t=" . $text . "<br>\n";
$this->setList($text);
$this->recursive($text, $i + 1);
}
}

public function getList()
{
$list = array();
$this->recursive("", 0);
return $this->_list;
}

// 順不同の文字列マッチ
// "aba" と　”aab”は一緒(true)
public static function isMatchInRandomOrder($text1, $text2)
{
$tips = self::split($text2);
$cnt = count($tips);
for ($i = 0; $i < $cnt; $i++) {
$searchString = $tips[$i];

$text1 = preg_replace("/{$searchString}/", "", $text1, 1);

if ($text1 == "")
{
break;
}
}

if ($text1 == "" && $i == count($tips) - 1)
{
return true;
}
return false;
}
}

$startTime = microtime(true);

$obj = new AllCombinationCharacter("abcdefgh");
foreach ($obj->getList() as $item) {
echo "t=" . $item . "<br>\n";
}

$endTime = microtime(true);
echo $endTime - $startTime . "秒";