PHP中字符串的排列 [英] Permutation for string in php

问题描述

在查找长度大于7的字符串的字符串置换时，我的代码有问题.例如，'abcdefgh'.我必须找到长度不超过12个字的排列.请查看我的代码，并建议是否可以进行任何优化.

I have problem with my code while finding permutation of string for string with length greater than 7. For eg 'abcdefgh'. I have to find the permutation of word up to 12 length. Please review my code and suggest if any optimization can be done.

function permute($str)
{
    if (strlen($str) < 2) 
    {
        return array($str);
    }

    $permutations = array();
    $tail = substr($str, 1);
    foreach (permute($tail) as $permutation) 
    {
        $length = strlen($permutation);

        for ($i = 0; $i <= $length; $i++) 
        {
            $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }

    /* Return the result */
    return $permutations;
}

$arr = permute('abcdefghijkl');

推荐答案

解决方案的核心似乎在于不检查所有内容.例如，如果您给我一个单词"earthquakes"，则应该立即清楚地发现没有字典单词以"qk"开头，因此不必检查所有格式为q k _ _ _ _ _ _ _ _ _的排列.这种检查将为您节省很多比较和查找操作.仅此"qk"示例将排除您需要检查的362,880(9！)个排列.

It seems like the core of the solution should lie in not checking everything. For example, if you give me the word "earthquakes", it should be immediately evident that there are no dictionary words for anything beginning with "qk", thus checking all permutations of the form q k _ _ _ _ _ _ _ _ _ is unnecessary. This type of check will save you a lot of comparison and lookup operations. This "qk" example alone would rule out 362,880 (9!) permutations that you would have needed to check otherwise.

因此，我将确保您生成的每个排列实际上首先是一个可能的单词，而不是计算所有排列，然后从字典中将其与排列之一匹配时从中拉出.

So instead of calculating ALL the permutations, then pulling from the dictionary if it matches one of the permutations, I would make sure that each permutation you're generating is actually a possible word first.

这篇关于PHP中字符串的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！