PHP如何详细实现字符串的全面排列方法？

本文共计711个文字，预计阅读时间需要3分钟。

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

例如，输入字符串abc，则打印出所有由字符a、b、c能组成的排列，包括：- abc- acb- bac- bca- cab- cba

思路：

1.利用递归形式构建递归树，每个节点代表一个字符的插入位置。

2.从第一个字符开始，递归地将剩余字符插入到递归树的所有可能位置。

3.每当递归到达叶子节点时，输出当前路径上所有字符组成的字符串，即为一种排列。

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

例如，输入字符串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"}