老大说这是求笛卡尔积,对于算法白痴的我只好依葫芦画瓢了。
话说11年的6月份,我提出这个问题,后来得到个js解法,匆忙结帖,快一年过去了,没有php解法,心里总有疙瘩,疙疙瘩瘩疙疙瘩瘩。今日旧事重提,我们一起来鞭尸。好像骄傲的青蛙后来跃跃欲试,可惜没联系上=========================
问题陈述有如下数据31,42...更多
32
43
35
36
...
更多根据上面的数据得到31,32,35,36
31,32.35,43
31,32,36,43
31,35,36,43
...上面这个结果位数是能够根据需求变化的,例如 4位的所有不重复组合 3位的所有不重复组合...再来个例子:
以下数据
01 02
03 04
05 06
07 08===========
得到组合结果(4位组合,要求可以根据条件得到不同位数的组合 例如3 2 )01 03 05 07
01 03 06 07
01 03 05 08
01 03 06 0801 04 05 07
01 04 05 08
01 04 06 07
01 04 06 0802 03 05 07
02 03 05 08
02 03 06 07
02 03 06 0802 04 05 07
02 04 05 08
02 04 06 07
02 04 06 08也可能是这个样子的问题
01 02
03 04
05 06
07 08 09 10
11
12 13没有固定行或者列的位数===============================
参考资料:1.类似问题第二弹,老徐有答案,不过第三弹跟第二弹比有了变化
http://topic.csdn.net/u/20110531/17/dd79391a-ed60-4050-b741-409cf1cbe6d2.html2.本问题的Js 解法
作者:JParser
function combo(m,n){
var arr=[],sumArr=[],str,isBreak=false;
for(var i=0;i <m;i++){
arr.push(0);
}
for(var i=0;i <n;i++){
arr[i]=1;
}
str=arr.join('');
while(1){
var itemArr=[],
reg=/(.*?)(10)/;
for(var j=0,len=str.length;j <len;j++){
str.charAt(j)!="0"&&itemArr.push(j);
}
sumArr.push(itemArr);
if(reg.test(str)){
str=str.replace(reg,function(l,s1,s2){
var num=s1.replace(/0/g,"").length,
prefixstr="";
for(var i=0,len=s1.length;i <len;i++){
prefixstr+=(i <num?'1':'0');
}
return prefixstr+"01";
});
}else{
break;
}
}
return sumArr;
}
function doubleCombo(arr,n){
var arrLen=arr.length,finalArr=[];
if(arrLen <n) {
alert("invalid input!");
return;
}
var comboCol=combo(arrLen,n);//行序号组合数
for(var i=0,cl=comboCol.length;i <cl;i++){//得到组合的每一项
var colItem=comboCol[i],items=[[]];
for(var j=0,il=colItem.length;j <il;j++){
var data=arr[colItem[j]];
if(typeof data=="number"){
for(var k=0,itemsLen=items.length;k <itemsLen;k++){
items[k].push(data);
}
}
else{
var mitems=[];
for(var m=0;m <items.length;m++){
for(var n=0;n <data.length;n++){
var mitem=items[m].concat([]);
mitem.push(data[n]);
mitems.push(mitem);
//console.log(mitem);
//console.log(mitems);
}
}
items=mitems;
}
}
finalArr=finalArr.concat(items);
}
return finalArr;
}
//下面是调用和结果显示
var t=doubleCombo([32,[24,34,43,44,46,47],35,36,42],3)
for(var k=0,l=t.length;k <l;k++){
var a=t[k];
for(var j=0,l2=a.length;j <l2;j++)
document.write(a[j]+' ');
document.write(' <br/>');
}
话说11年的6月份,我提出这个问题,后来得到个js解法,匆忙结帖,快一年过去了,没有php解法,心里总有疙瘩,疙疙瘩瘩疙疙瘩瘩。今日旧事重提,我们一起来鞭尸。好像骄傲的青蛙后来跃跃欲试,可惜没联系上=========================
问题陈述有如下数据31,42...更多
32
43
35
36
...
更多根据上面的数据得到31,32,35,36
31,32.35,43
31,32,36,43
31,35,36,43
...上面这个结果位数是能够根据需求变化的,例如 4位的所有不重复组合 3位的所有不重复组合...再来个例子:
以下数据
01 02
03 04
05 06
07 08===========
得到组合结果(4位组合,要求可以根据条件得到不同位数的组合 例如3 2 )01 03 05 07
01 03 06 07
01 03 05 08
01 03 06 0801 04 05 07
01 04 05 08
01 04 06 07
01 04 06 0802 03 05 07
02 03 05 08
02 03 06 07
02 03 06 0802 04 05 07
02 04 05 08
02 04 06 07
02 04 06 08也可能是这个样子的问题
01 02
03 04
05 06
07 08 09 10
11
12 13没有固定行或者列的位数===============================
参考资料:1.类似问题第二弹,老徐有答案,不过第三弹跟第二弹比有了变化
http://topic.csdn.net/u/20110531/17/dd79391a-ed60-4050-b741-409cf1cbe6d2.html2.本问题的Js 解法
作者:JParser
function combo(m,n){
var arr=[],sumArr=[],str,isBreak=false;
for(var i=0;i <m;i++){
arr.push(0);
}
for(var i=0;i <n;i++){
arr[i]=1;
}
str=arr.join('');
while(1){
var itemArr=[],
reg=/(.*?)(10)/;
for(var j=0,len=str.length;j <len;j++){
str.charAt(j)!="0"&&itemArr.push(j);
}
sumArr.push(itemArr);
if(reg.test(str)){
str=str.replace(reg,function(l,s1,s2){
var num=s1.replace(/0/g,"").length,
prefixstr="";
for(var i=0,len=s1.length;i <len;i++){
prefixstr+=(i <num?'1':'0');
}
return prefixstr+"01";
});
}else{
break;
}
}
return sumArr;
}
function doubleCombo(arr,n){
var arrLen=arr.length,finalArr=[];
if(arrLen <n) {
alert("invalid input!");
return;
}
var comboCol=combo(arrLen,n);//行序号组合数
for(var i=0,cl=comboCol.length;i <cl;i++){//得到组合的每一项
var colItem=comboCol[i],items=[[]];
for(var j=0,il=colItem.length;j <il;j++){
var data=arr[colItem[j]];
if(typeof data=="number"){
for(var k=0,itemsLen=items.length;k <itemsLen;k++){
items[k].push(data);
}
}
else{
var mitems=[];
for(var m=0;m <items.length;m++){
for(var n=0;n <data.length;n++){
var mitem=items[m].concat([]);
mitem.push(data[n]);
mitems.push(mitem);
//console.log(mitem);
//console.log(mitems);
}
}
items=mitems;
}
}
finalArr=finalArr.concat(items);
}
return finalArr;
}
//下面是调用和结果显示
var t=doubleCombo([32,[24,34,43,44,46,47],35,36,42],3)
for(var k=0,l=t.length;k <l;k++){
var a=t[k];
for(var j=0,l2=a.length;j <l2;j++)
document.write(a[j]+' ');
document.write(' <br/>');
}
即集合中的每一个元素都要与右边集合的每一个元素构成新的集合对于你的问题,应先求组合,再求笛卡尔积(如果不包含集合,就不用求了)不太理解
得到组合结果(4位组合,要求可以根据条件得到不同位数的组合 例如3 2 )
这句话的意思
话说你找的那个js解法怎么有重复结果的。
<?php
$array[] = array('01','02');
$array[] = array('03','04');
$array[] = array('05','06');
$array[] = array('07','08','09','10');
$array[] = array('11');
$array[] = array('12','13');
/** 笛卡尔 **/
function merge( $array,$c = array())
{
if(!$array) return $c;
$na = array_shift( $array );
if(!$c) return merge($array,$na);
foreach( $c as $k=>$v)
{
foreach( $na as $nv ) $tmp[] = $v."-".$nv;
}
$c = $tmp;
return merge($array,$c);
}
/** M 取N **/
function combination($numArr,$combineLen)
{
$numCt = count($numArr);
if($combineLen > $numCt) return;
$bin = str_pad('',$combineLen,'1');
$bin = str_pad($bin,$numCt,'0',STR_PAD_RIGHT);
$find = $bin;
$rs[] = implode(',',array_slice($numArr,0,$combineLen));
$j = 1;
while(strrev($find) != $bin)
{
$k = explode('10',$find,2);
$find = $find{0} === '0' ? strrev($k[0]).'01'.$k[1] : $k[0].'01'.$k[1];
for($i=0;$i<$numCt;$i++) $rs[$j] .= $find[$i] ? $numArr[$i] . "," : '';
$j++;
}
return $rs;
}
/**先从数组M中取N个组合,然后对这些组合求笛卡尔值*/
function main( $array ,$n)
{
$s = combination(range(1,count($array)),$n);
$ret = array();
foreach($s as $keys)
{
$arr = array();
foreach(explode(',',trim($keys,',')) as $key)
{
$arr[] = $array[$key-1];
}
$ret[] = merge( $arr );
}
return call_user_func_array('array_merge',$ret);
}
echo "<pre/>";
print_r(main($array,4));
?>
array('01', '02'),
array('03', '04'),
array('05', '06'),
array('07', '08'),
);/*** 先求组合 ***/
$comb = combination(array_keys($ar), 3);/*** 再求笛卡尔积 ***/
$res = array();
foreach($comb as $r) {
$t = array();
foreach($r as $k) $t[] = $ar[$k];
$res = array_merge($res, Descartes($t));
}/*** 输出结果 ***/
print_r($res);
/*** 笛卡尔积 ***/
function Descartes() {
$t = func_get_args();
if(func_num_args() == 1) return call_user_func_array( __FUNCTION__, $t[0] );
$a = array_shift($t);
if(! is_array($a)) $a = array($a);
$a = array_chunk($a, 1);
do {
$r = array();
$b = array_shift($t);
if(! is_array($b)) $b = array($b);
foreach($a as $p)
foreach(array_chunk($b, 1) as $q)
$r[] = array_merge($p, $q);
$a = $r;
}while($t);
return $r;
}/*** 组合 ***/
function 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[] = $t;
}
return $res;
}
$arr = array(
array(1),
array(2,3),
array(4,5,6)
);
fun($arr);
print_r($res);
function fun($arr, $tmp = array())
{
foreach(array_shift($arr) AS $v)
{
$tmp[] = $v;
if($arr)
{
fun($arr, $tmp);
}
else
{
$GLOBALS["res"][] = $tmp;
}
array_pop($tmp);
}
}
/**** print
Array
(
[0] => Array
(
[0] => 1
[1] => 2
[2] => 4
) [1] => Array
(
[0] => 1
[1] => 2
[2] => 5
) [2] => Array
(
[0] => 1
[1] => 2
[2] => 6
) [3] => Array
(
[0] => 1
[1] => 3
[2] => 4
) [4] => Array
(
[0] => 1
[1] => 3
[2] => 5
) [5] => Array
(
[0] => 1
[1] => 3
[2] => 6
))
/****/
1 2 4
1 3 4
1 2 5
1 3 5
1 2 6
1 3 6
$arr = array(
array(1),
array(2,3),
array(4,5,6)
);
fun($arr, 2);
print_r($res);
function fun($arr, $len, $tmp = array())
{
if($arr)
{
$num = sizeof($tmp);
if($num < $len)
{
foreach(array_shift($arr) AS $v)
{
$tmp[] = $v;
if($num == $len-1)
{
$GLOBALS["res"][] = $tmp;
}
else
{
fun($arr, $len, $tmp);
}
array_pop($tmp);
}
fun($arr, $len, $tmp);
}
}
}