PHP实现字符串的全排列详解

yipeiwu_com5年前PHP代码库

输入一个字符串,按字典序打印出该字符串中字符的所有排列。

例如,输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路:
1.利用递归形成递归树,达到深度优先,固定首字母的效果

2.得复位以后才能再次深度优先

3.回溯法思想

4.一张图和一个运行过程,只能慢慢体会了

<?phpfunction test($str,$start,&$res){    //递归终止条件

    if($start==strlen($str)){        $res[]=$str;        return;

    }  

    // 

    for($i=$start;$i<strlen($str);++$i){        if($i==$start || $str{$i}!=$str{$start}){

            swap($str,$i,$start);var_dump($str.'==='.$start);var_dump($res);sleep(1);

            test($str,$start+1,$res);

            swap($str,$i,$start);

        }  

   

    }  

    return $res;

}function swap(&$str,$a,$b){    

if(!is_string($str)) return;    

$t=$str{$a};    

$str{$a}=$str{$b};    

$str{$b}=$t;

}$str="abc";$res=array();//调用入口,从索引0开始

$res=test($str,0,$res);

var_dump($res);
string(7) "abc===0"array(0) {

}string(7) "abc===1"array(0) {

}string(7) "abc===2"array(0) {

}string(7) "acb===1"array(1) {

 [0]=> string(3) "abc"}string(7) "acb===2"array(1) {

 [0]=> string(3) "abc"}string(7) "bac===0"array(2) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"}string(7) "bac===1"array(2) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"}string(7) "bac===2"array(2) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"}string(7) "bca===1"array(3) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"}string(7) "bca===2"array(3) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"}string(7) "cba===0"array(4) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"}string(7) "cba===1"array(4) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"}string(7) "cba===2"array(4) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"}string(7) "cab===1"array(5) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"

 [4]=> string(3) "cba"}string(7) "cab===2"array(5) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"

 [4]=> string(3) "cba"}array(6) {

 [0]=> string(3) "abc"

 [1]=> string(3) "acb"

 [2]=> string(3) "bac"

 [3]=> string(3) "bca"

 [4]=> string(3) "cba"

 [5]=> string(3) "cab"}

相关文章

实用PHP会员权限控制实现原理分析

实用PHP会员权限控制实现原理分析

我的通用权限系统设计是更换权限时候尽量不要涉及到代码修改,来自chinaunix论坛,今天转过来看看。希望对大家有所帮助,对PHP100的朋友有个很高的提升。 复制代码 代码如下: /*...

百度工程师讲PHP函数的实现原理及性能分析(二)

百度工程师讲PHP函数的实现原理及性能分析(二)

类方法 类方法其执行原理和用户函数是相同的,也是翻译成opcodes顺次调用。类的实现,zend用一个数据结构zend_class_entry来实现,里面保存了类相关的一些基本信息。这个...

php自定义hash函数实例

本文实例讲述了php自定义hash函数实现方法。分享给大家供大家参考。具体分析如下: 这里演示php实现的一个简单hash算法,可以用来加密,不过这个函数过于简单,不能用来解密 fu...

php一行代码获取文件后缀名实例分析

本文实例讲述了php一行代码获取文件后缀名的方法。分享给大家供大家参考。具体方法分析如下: php中一行代码获取文件后缀名的方法要结合很多的函数了,我们这个有点像asp中的函数了,下面来...

2款PHP无限级分类实例代码

本文章总结了两款PHP无限级分类实现程序代码,有需要学习的朋友可参考一下。 主要思路:首先看第三行和第四行,父类ID(PARENTID)的值是1,表示属于id=1这个类的子类,而,一,二...