输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
字符串的排列组合其实是深度优先遍历和回溯法。啊哈算法上提到过解决方案，可以想想一个人拿着一些数字分别向盒子里面放。假设先将a放在第一个盒子，第二个盒子可以放b和c，假设放b，第三个只能放c。然后手里没有字母了。一次排列完成。然后开始回退，假设第三个不放c该放什么，自然是没有选择。因为前两个已经放了a，b。再退一步如果第二个没有放b，此时手里有b和c。然后从出了b外的字母选择下放入后开始向后面接着放手里包含的,注释在代码中。
$books = array(0,0,0,0,0,0,0,0,0);
$sequence = array();
$all_result = array();
function Permutation($str)
{
// write code here
if(strlen($str)==0){
return array();
}
GLOBAL $all_result;
$all_result = array();
$arrays = str_split($str);
printstr($arrays,0,count($arrays));
$all_result = array_unique($all_result);
return $all_result;
}
/*
排列arr里面的字母，当前的位置为cur，总长度为length
*/
function printstr($arr, $cur, $length){
GLOBAL $books,$sequence,$all_result;
if($cur==$length){ // 表示一次排列已经完成
$all_result[] = implode('',$sequence);
return;
}
else{
for($i = 0; $i < count($arr); $i++){
if($books[$i] == 0){ // books表示标记对于位置的字母是否被用了。没有被用是0
$books[$i] = 1;
$sequence[$cur] = $arr[$i]; //将没有被用的放到排列后面
printstr($arr,$cur+1,$length);//在放入当前元素后，从没有放入的元素里面接着完成length-cur的长度排列
$books[$i] = 0;//上面完成后将状态改变为没有使用，因为每次排列都是独立的。
}
}
}
}
