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” }