PHP_字典序法获得排列组合
浏览数：125 /
时间：2015年06月09日
前段时间一次聚会闲聊时聊到一个问题，就是给你一排数组，例如1,2,3,4,5,如何能高效的获取上述数列的所有排列组合，正巧没事，研究了一下，一开始以为是个很简单的问题，就直接开始写代码了，后来发现怎么循环也不理想，基本上都有一些不必要的消耗，百度一下看到一个不错的算法，字典序法，顺便学习一下，然后记录之。
摘一段算法思想：
设P是[1,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|Pi<Pi+1}, k=max{i|Pi>Pj} ,对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转， P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个
例子:839647521的下一个排列.
从最右开始,找到第一个比右边小的数字4(因为4<7，而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5),交换4、5,此时5右边为7421,倒置为1247,即得下一个排列:839651247.用此方法写出全排列的非递归算
感觉还是挺明了的，在纸上稍微写了一下，然后稍作验证，确实不错，然后自己用PHP实现了一下：
/*
字典序法获取所有排列
@最后更新时间：03/05/2014
@作者：toryzen(toryzen.com)
@备注，备注中示例用ABC顺序表示
*/
function
getPars(
$arr
){
//正向排列
sort(
$arr
);
//获取数组长度
$len
=
count
(
$arr
)-1;
//记录传入的排列
$return
[] =
$arr
;
while
(TRUE){
//从右侧开始找到第一个左侧(A)<右侧(B)的数字序列
for
(
$i
=
$len
;
$i
>=0;
$i
--){
if
(
$arr
[
$i
]>
$arr
[
$i
-1]){
$here
=
$i
-1;
break
;
}
}
//若找到了则开始换位
if
(
$here
>=0){
//从有右向左侧找，第一个比左侧(A)大的数字(C)交换位置得到CBA
for
(
$j
=
$len
;
$j
>
$here
;
$j
--){
if
(
$arr
[
$here
]<
$arr
[
$j
]){
$revers
=
$j
;
list(
$arr
[
$here
],
$arr
[
$j
]) =
array
(
$arr
[
$j
],
$arr
[
$here
]);
break
;
}
}
//将后续数字倒序得到CAB
unset(
$newarr
);
for
(
$h
=
$here
+1;
$h
<=
$len
;
$h
++){
$newarr
[] =
$arr
[
$h
];
unset(
$arr
[
$h
]);
}
$return
[] =
$arr
=
array_merge
(
$arr
,
array_reverse
(
$newarr
,TRUE));
}
else
{
break
;
}
}
return
$return
;
}
$arr
=
array
(1,4,3,2);
print_r(getPars(
$arr
));
|
除了这个还有一个递归法，But自己的递归学的不是很好，而且所有的递归都能用循环解决随用循环，改天有时间，再研究一下递归，老是转不过弯来。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
