笛卡尔积

@date:2016-08-30 22:39:00

在数学中,两个集合X和Y的笛卡尓积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

假设集合A={a, b},集合B={0, 1, 2},则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。

编程里笛卡尓积常用于生成商品的各种规格。

实现 #

PHP #

<?php  
    $color = array('红', '黄', '黑');  
    $size = array(39, 40, 41);  
    $local = array('男', '女');  
      
    echo "<pre>";  
    echo json_encode(combineDika($local, $color, $size));  
      
    /** 
     * 所有数组的笛卡尔积 
     * 
     * @param unknown_type $data 
     */  
    function combineDika() {  
        $data = func_get_args();  
        $cnt = count($data);
  
        $result = array();  
        foreach($data[0] as $item) {  
            $result[] = array($item); //取出第一个数组里的各个元素组成新的二元数组,示例: array('红', '黄', '黑') 转为 array(array('红'),array('黄'), array('黑'))
        }
  
        for($i = 1; $i < $cnt; $i++) {
            //追加后续数组的元素到第一个数组里  
            $result = combineArray($result,$data[$i]);  
        }  
        return $result;  
    }  
       
    /** 
     * 两个数组的笛卡尔积 
     * 
     * @param unknown_type $arr1 ,示例: array(array('红'),array('黄'), array('黑'))
     * @param unknown_type $arr2 
     */  
    function combineArray($arr1,$arr2) {  
        $result = array();  
        foreach ($arr1 as $item1) {  
            foreach ($arr2 as $item2) {  
                $temp = $item1; // $item1是数组
                $temp[] = $item2;  //追加上元素$item2
                $result[] = $temp;  //组成新数组
            }  
        }  
        return $result;  
    }  
?>  

结果:

[
    ["男", "红", 39],
    ["男", "红", 40],
    ["男", "红", 41],
    ["男", "黄", 39],
    ["男", "黄", 40],
    ["男", "黄", 41],
    ["男", "黑", 39],
    ["男", "黑", 40],
    ["男", "黑", 41],
    ["女", "红", 39],
    ["女", "红", 40],
    ["女", "红", 41],
    ["女", "黄", 39],
    ["女", "黄", 40],
    ["女", "黄", 41],
    ["女", "黑", 39],
    ["女", "黑", 40],
    ["女", "黑", 41]
]

JavaScript #

这里可根据给的对象或者数组生成笛卡尔积

//笛卡儿积组合
function descartes(list)
{
  //parent上一级索引;count指针计数
  var point = {};
  var result = [];
  var pIndex = null;
  var tempCount = 0;
  var temp  = [];
  //根据参数列生成指针对象
  for(var index in list)
  {
    if(typeof list[index] == 'object')
    {
      point[index] = {'parent':pIndex,'count':0}
      pIndex = index;
    }
  }
  //单维度数据结构直接返回
  if(pIndex == null)
  {
    return list;
  }
  //动态生成笛卡尔积
  while(true)
  {
    for(var index in list)
    {
      tempCount = point[index]['count'];
      temp.push(list[index][tempCount]);
    }
    //压入结果数组
    result.push(temp);
    temp = [];
    //检查指针最大值问题
    while(true)
    {
      if(point[index]['count']+1 >= list[index].length)
      {
        point[index]['count'] = 0;
        pIndex = point[index]['parent'];
        if(pIndex == null)
        {
          return result;
        }
        //赋值parent进行再次检查
        index = pIndex;
      }
      else
      {
        point[index]['count']++;
        break;
      }
    }
  }
}

示例:

var list = [['男','女'], ['红', '黄', '黑'], [39, 40, 41]];
var res = descartes(list);

Build by Loppo 0.6.14