排列在PHP

字符串我有問題，我的代碼，同時尋找串的排列字符串長度大於7.如「ABCDEFGH」更大。我必須找到長達12字的字排列。請查看我的代碼並建議是否可以完成任何優化。排列在PHP

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');

來源

2011-11-15 ratna

可以估算出*號*長度的字符串的排列'N'，以及如何之快，數量的增長？ –

它有什麼問題？排列在O（n！）中運行，因此需要很長時間才能將12個長度的字符串運行爲12！是一個很大的數字。 –

儘管在多項式時間中生成第n個排列是有一個技巧的，但如果你想要所有的排列，你需要計算所有的n！其中。 –

這似乎是解決方案的核心應該在於不檢查一切。例如，如果你給我這個詞「地震」，它應該是一目瞭然的，有與「QK」開始沒有任何字典單詞，所以檢查的形式q k _ _ _ _ _ _ _ _ _是不必要的所有排列。這種檢查將爲您節省大量比較和查找操作。僅僅這個「qk」的例子就可以排除362,880（9！）個排列組合，否則你需要進行檢查。

因此，而不是計算所有的排列，然後從字典拉動，如果它匹配排列的一個，我會確保每個排列你產生實際上是一個可能的單詞第一。

來源

2011-11-15 02:12:06

回答

相關問題