php实现的生成排列算法示例-php开发

这篇文章主要介绍了php实现的生成排列算法,结合实例形式分析了php基于递归、遍历字符串实现全排列相关算法实现技巧,需要的朋友可以参考下

本文实例讲述了php实现的生成排列算法。分享给大家供大家参考，具体如下：


<?php
function perm($s, $n, $index)
{
  if($n == 0)
  {
     return '';
  }
  else
  {
    $nIndex = count($index);  //可用的字符串下标
    $res = array();
    foreach($index as $i => $v)
    {
      $tmp = $index;
      unset($tmp[$i]);    //去掉当前的前缀
      /* 调试信息，便于理解
      echo "len $n , cur $i , index:\n";
      var_dump($tmp);
       */
      $ret = perm($s, $n-1, $tmp);  //递归得到稍短的排列
      if($ret != '')
      {
        foreach($ret as $r)
        {
          $res[] = $s[$v] . $r;  //将稍短的排列逐个拼上当前的前缀
        }
      }
      else
      {
        $res[] = $s[$v];
      }
    }
    return $res;
  }
}
function getPerm($s)
{
  $n = strlen($s);
  $index = range(0, $n-1);
  //得到不同长度的排列
  for($i=1; $i<=$n; $i++)
  {
    var_dump(perm($s, $i, $index));
  }
}
getPerm('abcd');
?>

运行结果：

array(4) {
[0]=>
string(1) "a"
[1]=>
string(1) "b"
[2]=>
string(1) "c"
[3]=>
string(1) "d"
}
array(12) {
[0]=>
string(2) "ab"
[1]=>
string(2) "ac"
[2]=>
string(2) "ad"
[3]=>
string(2) "ba"
[4]=>
string(2) "bc"
[5]=>
string(2) "bd"
[6]=>
string(2) "ca"
[7]=>
string(2) "cb"
[8]=>
string(2) "cd"
[9]=>
string(2) "da"
[10]=>
string(2) "db"
[11]=>
string(2) "dc"
}
array(24) {
[0]=>
string(3) "abc"
[1]=>
string(3) "abd"
[2]=>
string(3) "acb"
[3]=>
string(3) "acd"
[4]=>
string(3) "adb"
[5]=>
string(3) "adc"
[6]=>
string(3) "bac"
[7]=>
string(3) "bad"
[8]=>
string(3) "bca"
[9]=>
string(3) "bcd"
[10]=>
string(3) "bda"
[11]=>
string(3) "bdc"
[12]=>
string(3) "cab"
[13]=>
string(3) "cad"
[14]=>
string(3) "cba"
[15]=>
string(3) "cbd"
[16]=>
string(3) "cda"
[17]=>
string(3) "cdb"
[18]=>
string(3) "dab"
[19]=>
string(3) "dac"
[20]=>
string(3) "dba"
[21]=>
string(3) "dbc"
[22]=>
string(3) "dca"
[23]=>
string(3) "dcb"
}
array(24) {
[0]=>
string(4) "abcd"
[1]=>
string(4) "abdc"
[2]=>
string(4) "acbd"
[3]=>
string(4) "acdb"
[4]=>
string(4) "adbc"
[5]=>
string(4) "adcb"
[6]=>
string(4) "bacd"
[7]=>
string(4) "badc"
[8]=>
string(4) "bcad"
[9]=>
string(4) "bcda"
[10]=>
string(4) "bdac"
[11]=>
string(4) "bdca"
[12]=>
string(4) "cabd"
[13]=>
string(4) "cadb"
[14]=>
string(4) "cbad"
[15]=>
string(4) "cbda"
[16]=>
string(4) "cdab"
[17]=>
string(4) "cdba"
[18]=>
string(4) "dabc"
[19]=>
string(4) "dacb"
[20]=>
string(4) "dbac"
[21]=>
string(4) "dbca"
[22]=>
string(4) "dcab"
[23]=>
string(4) "dcba"
}