高分求一個算法,在线等待可馬上結貼 本帖最后由 sibang 于 2013-08-08 23:44:40 编辑 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 做了一点点进展,谈不上算法,效率很低! 只是希望能帮你打开思路...思路:先算排列,然后去除排列中重复的地方,来达成组合.P.S:半路出家,做了一年多PHP了,居然完全不知道数据结构、算法... 手头项目完成后一定好好补补课../*$arr = array("A","B","C");Function getArray($arr,$len=2){ $arr2 = array(); foreach ($arr as $y){ foreach($arr as $k){ if($y != $k){ $arr2[] = $y.$k; } } } $arr3 = array(); foreach($arr2 as $c){ $f = str_split($c); if($arr3){ $i = 0; foreach($arr3 as $d){ $e = str_split($d); if(in_array($f[0],$e) && in_array($f[1],$e)){ $i++; } } if(!$i){ $arr3[] = $c; } }else{ $arr3[] = $c; } } return $arr3;}*/$arr = array("A","B","C","D");Function getArray($arr,$len=3){ $arr2 = array(); foreach ($arr as $y){ //$len是几,就循环几次,这里是一个变数 foreach($arr as $k){ foreach($arr as $v){ if($y != $k && $y != $v && $v != $k){ //$len个元素均不相同 $arr2[] = $y.$k.$v; } } } } $arr3 = array(); foreach($arr2 as $c){ $f = str_split($c); if($arr3){ $i = 0; foreach($arr3 as $d){ $e = str_split($d); if(in_array($f[0],$e) && in_array($f[1],$e) && in_array($f[2],$e)){ //$len个元素都在数组中的话,$i++ 如果$i大于0,这个记录就抛弃 $i++; } } if(!$i){ $arr3[] = $c; } }else{ $arr3[] = $c; } } return $arr3;}print_r(getArray($arr));有三处会根据$len变化,而ABCD四个字符或者ABCDE五个字符均可正确得出结果所以关键在$len这里如何判断和递归...==============================总觉得这个方法很山寨,求批评指正 A B C D E F G 七个字符的数组, 取三个排列用上边的方法 结论是Array ( [0] => ABC [1] => ABD [2] => ABE [3] => ABF [4] => ABG [5] => ACD [6] => ACE [7] => ACF [8] => ACG [9] => ADE [10] => ADF [11] => ADG [12] => AEF [13] => AEG [14] => AFG [15] => BCD [16] => BCE [17] => BCF [18] => BCG [19] => BDE [20] => BDF [21] => BDG [22] => BEF [23] => BEG [24] => BFG [25] => CDE [26] => CDF [27] => CDG [28] => CEF [29] => CEG [30] => CFG [31] => DEF [32] => DEG [33] => DFG [34] => EFG ) 35个 应该是正确的..... 你这是求“组合”方法有很多种我先给你一种“高效率的10移动法”,函数命名选用组合的英文单词combinationfunction combination( $arr, $num=0) { $len = count($arr); if($num == 0) $num = $len; $res = array(); for($i=1,$n=pow(2, $len);$i<$n;++$i) { $tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT); $t = array(); for($j=0;$j<$len;++$j) { if($tmp{$j} == '1') { $t[] = $arr[$j]; } } if(count($t) == $num) $res[] = join('', $t); } return $res;}调用:$arr = array('A', 'B', 'C');print_r(combination($arr, 2));Array( [0] => BC [1] => AC [2] => AB) 是否有重复字母?还有AB,BA算不算不同的?总得要具体说明一下吧 递归的写法function combination($ar, $k, $m=0, $a=array()) { static $ret = array(); if($m == 0) { $m = count($ar); $ret = array(); } for($i=$m; $i>=$k; $i--) { $a[$k-1] = $ar[$i-1]; if($k > 1) { combination(&$ar, $k-1, $i-1, $a); }else { array_unshift ($ret, array_reverse($a)); } } return $ret;}利用堆栈的写法function combination($ar, $num) { $control = range(0, $num-1); $k = false; $total = count($ar); while($control[0] < $total-($num-1)) { $t = array(); for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]]; $r[] = $t; for($i=$num-1; $i>=0; $i--) { $control[$i]++; for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1; if($control[$i] < $total-($num-$i-1)) break; } } return $r;} 版大犀利求问6#为甚么使用pow(2,$len)来做循环次数, 而为什么可以通过转化为2进制数来解决问题? 这一块应该是数学问题了吧.... 但是没想明白, 求点拨... 2进制那个简单的,你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的,他这个是根据取的长度在前面增加几个0,然后可以循环才能有if($tmp{$j} == '1') { $t[] = $arr[$j]; }这个数组,这个数组的长度才能与$len相同,相同的话就组成字符串 2进制那个简单的,你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的,他这个是根据取的长度在前面增加几个0,然后可以循环才能有if($tmp{$j} == '1') { $t[] = $arr[$j]; }这个数组,这个数组的长度才能与$len相同,相同的话就组成字符串大概略微有点头绪了是不是二进制数010101之类的 恰好可以代表每个位置选中/未选中pow(2,$len)可以大于等于所有的排列情况的数量,而小于它的数,每个数的2进制形式也都是不同的,所以恰好可以用这种方式来进行筛选?还没想透,不知道如何证明或者反证这种巧妙的方法 .... 再纠结下 可参阅 http://blog.sina.com.cn/s/blog_605f5b4f0100vcwz.html 做了10萬次循環測試,發現下邊這個效率最高,結貼了,感謝xuzuning老大的幫忙function combination($ar, $num) { $control = range(0, $num-1); $k = false; $total = count($ar); while($control[0] < $total-($num-1)) { $t = array(); for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]]; $r[] = $t; for($i=$num-1; $i>=0; $i--) { $control[$i]++; for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1; if($control[$i] < $total-($num-$i-1)) break; } } return $r;} php pdo 连接 mssql 超时 是怎么回事啊? c语言或者asp 实现图片无损压缩 PHP如何通过代码来新建立一个MYSQL新表 关于全文索引,普通索引和无索引,在中文和英文上;做了一组测试,但结果很让人迷茫;请高手指点! 有没有好点的php+ajax分页的代码? 上传图片出错,这段代码我以前用的时候没报错 求职,有大哥大姐帮忙介绍吗?内有个个人简历 帮忙查错 如何得到在服务器创建读写文件的权限? php插入数据乱码,全部设置都为UTF-8 1.如何判断时间格式是否正确 2.如何判断用户登录权限 从数据库依次查询关键字,再通过关键字查询结果,再插入数据的操作
/*
$arr = array("A","B","C");
Function getArray($arr,$len=2){
$arr2 = array();
foreach ($arr as $y){
foreach($arr as $k){
if($y != $k){
$arr2[] = $y.$k;
}
}
}
$arr3 = array();
foreach($arr2 as $c){
$f = str_split($c);
if($arr3){
$i = 0;
foreach($arr3 as $d){
$e = str_split($d);
if(in_array($f[0],$e) && in_array($f[1],$e)){
$i++;
}
}
if(!$i){
$arr3[] = $c;
}
}else{
$arr3[] = $c;
}
} return $arr3;
}*/$arr = array("A","B","C","D");
Function getArray($arr,$len=3){
$arr2 = array();
foreach ($arr as $y){ //$len是几,就循环几次,这里是一个变数
foreach($arr as $k){
foreach($arr as $v){
if($y != $k && $y != $v && $v != $k){ //$len个元素均不相同
$arr2[] = $y.$k.$v;
}
}
}
}
$arr3 = array();
foreach($arr2 as $c){
$f = str_split($c);
if($arr3){
$i = 0;
foreach($arr3 as $d){
$e = str_split($d);
if(in_array($f[0],$e) && in_array($f[1],$e) && in_array($f[2],$e)){ //$len个元素都在数组中的话,$i++ 如果$i大于0,这个记录就抛弃
$i++;
}
}
if(!$i){
$arr3[] = $c;
}
}else{
$arr3[] = $c;
}
} return $arr3;
}
print_r(getArray($arr));
有三处会根据$len变化,而ABCD四个字符或者ABCDE五个字符均可正确得出结果所以关键在$len这里如何判断和递归...==============================
总觉得这个方法很山寨,求批评指正
Array ( [0] => ABC [1] => ABD [2] => ABE [3] => ABF [4] => ABG [5] => ACD [6] => ACE [7] => ACF [8] => ACG [9] => ADE [10] => ADF [11] => ADG [12] => AEF [13] => AEG [14] => AFG [15] => BCD [16] => BCE [17] => BCF [18] => BCG [19] => BDE [20] => BDF [21] => BDG [22] => BEF [23] => BEG [24] => BFG [25] => CDE [26] => CDF [27] => CDG [28] => CEF [29] => CEG [30] => CFG [31] => DEF [32] => DEG [33] => DFG [34] => EFG )
35个 应该是正确的.....
我先给你一种“高效率的10移动法”,函数命名选用组合的英文单词combinationfunction combination( $arr, $num=0) {
$len = count($arr);
if($num == 0) $num = $len;
$res = array();
for($i=1,$n=pow(2, $len);$i<$n;++$i) {
$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);
$t = array();
for($j=0;$j<$len;++$j) {
if($tmp{$j} == '1') {
$t[] = $arr[$j];
}
}
if(count($t) == $num) $res[] = join('', $t);
}
return $res;
}调用:
$arr = array('A', 'B', 'C');
print_r(combination($arr, 2));
Array
(
[0] => BC
[1] => AC
[2] => AB
)
是否有重复字母?
还有AB,BA算不算不同的?
总得要具体说明一下吧
static $ret = array();
if($m == 0) {
$m = count($ar);
$ret = array();
}
for($i=$m; $i>=$k; $i--) {
$a[$k-1] = $ar[$i-1];
if($k > 1) {
combination(&$ar, $k-1, $i-1, $a);
}else {
array_unshift ($ret, array_reverse($a));
}
}
return $ret;
}利用堆栈的写法function combination($ar, $num) {
$control = range(0, $num-1);
$k = false;
$total = count($ar);
while($control[0] < $total-($num-1)) {
$t = array();
for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]];
$r[] = $t; for($i=$num-1; $i>=0; $i--) {
$control[$i]++;
for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1;
if($control[$i] < $total-($num-$i-1)) break;
}
}
return $r;
}
2进制那个简单的,你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的,他这个是根据取的长度在前面增加几个0,然后可以循环才能有
if($tmp{$j} == '1') {
$t[] = $arr[$j];
}
这个数组,这个数组的长度才能与$len相同,相同的话就组成字符串
2进制那个简单的,你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的,他这个是根据取的长度在前面增加几个0,然后可以循环才能有
if($tmp{$j} == '1') {
$t[] = $arr[$j];
}
这个数组,这个数组的长度才能与$len相同,相同的话就组成字符串大概略微有点头绪了是不是二进制数010101之类的 恰好可以代表每个位置选中/未选中pow(2,$len)可以大于等于所有的排列情况的数量,而小于它的数,每个数的2进制形式也都是不同的,所以恰好可以用这种方式来进行筛选?还没想透,不知道如何证明或者反证这种巧妙的方法 .... 再纠结下
$control = range(0, $num-1);
$k = false;
$total = count($ar);
while($control[0] < $total-($num-1)) {
$t = array();
for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]];
$r[] = $t; for($i=$num-1; $i>=0; $i--) {
$control[$i]++;
for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1;
if($control[$i] < $total-($num-$i-1)) break;
}
}
return $r;
}