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

yipeiwu_com7年前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 $url=$_GET['url']; $ext=pathinfo($url,PATHINFO_EXTENSION); if($ext!='jpg'...

windows环境下php配置memcache的具体操作步骤

windows环境下php配置memcache的具体操作步骤

首先要安装好php和apache环境。我用的是wamp整合的套件php 5.2.8apache 2.2.1.1这些都准备好了后,就到 memcache 官网去下载 windows 下的...

php下通过IP获取地理位置的代码(小偷程序)

复制代码 代码如下: function get_ip_place() { $ip=file_get_contents("http://fw.qq.com/ipaddress"); $ip...

php编写批量生成不重复的卡号密码代码

闲的蛋疼的时候,顺便加强下自己对PHP中数组操纵的一些技巧,就写了下面的一段小代码,可以随机生成卡号密码对应的数组,并且自动去重复,思路没有,纯粹瞎掰。 <?php h...

PHP 线程安全与非线程安全版本的区别深入解析

从2000年10月20日发布的第一个Windows版的PHP3.0.17开始的都是线程安全的版本,这是由于与Linux/Unix系统是采用多进程的工作方式不同的是Windows系统是采用...