遇到了一个求m个数中任选n个的全部组合算法,在网上查了好久,决定自己写一个.顺便写了元素交换函数和替代print_r的数组元素显示函数,毕竟我们更习惯于{*,*,*,*}的数组显示风格,但是这个函数只支持一维数组哟.
说明一下,这个函数只是生成了组合元素的二进制版本,你还需要将其转换为自己需要的数组.比如我这里生成的一个组合为:{1,1,0,0,1},表示去5个数中第1,2,5个元素.其他类推.还有什么问题给我联系.
function
swap(
&
$a
,&
$b
){ //交换函数
$temp
=
$a
;
$a
=
$b
;
$b
=
$temp
;}
function
printarray(
$a
){ //用我们习惯的方式显示数组元素
echo
"
{
"
;
foreach
(
$a
as
$k
=>
$v
){
if
(
$k
==
0
)
echo
$v
;
else
echo
"
,
"
.
$v
; }
echo
"
}
"
; }
function
zuhe(
$m
,
$n
){
//求m个数中任意n个数的组合
for($i=0;$i<$n;$i++) $p[$i] = 1; //前n个数置1,后面的都为0for ( $i = $n ; $i < $m ; $i ++ ) $p [ $i ] = 0 ;
printarray($p);
$pp
=
$n
-
1
; //下一步要交换的1的位置
$pt = $m; //尾部指针,记录当前要交换0的截至位置
while
(
$pp
>=
0
){
$p1
=
$pp
; //当前要交换的值为1的位置(也就是指针)
$p0
=
$pp
+
1
; //要交换的值为0的位置
while
(
$p0
<
$pt
){ //要交换的0还未到截至位置
swap(
$p
[
$p1
]
,
$p
[
$p0
]); //0和1交换
printarray(
$p
);
$p1
++
; //指针后移
$p0
++
;
}
$pp
--
; //下一步要交换的1的位置前移
while
(
$pp
>=
0
){
$p1
=
$pp
; //当前要交换的值为1的位置(也就是指针)
$p0
=
$pp
+
1
; //要交换的值为0的位置
while
(
$p0
<
$pt
){ //要交换的0还未到截至位置 swap(
$p
[
$p1
]
,
$p
[
$p0
]); //0和1交换
printarray(
$p
);
$p1
++
; //指针后移
$p0
++
; }
$pp
--
; //下一步要交换的1的位置前移
$pt--; //要交换0的截至位置前移
}
}
zuhe(
8
,
5
); //测试从8个数中选5个的组合
}}zuhe(
8
,
5
); //测试从8个数中选5个的组合