php - 具有互斥性的二维数组的所有组合

Question

我有一个如下所示的数组:

$i[0] = ['a', 'b', 'c'];
$i[1] = ['d', 'e'];
$i[2] = ['a', 'b', 'c'];
$i[3] = ['d', 'e'];
$i[4] = ['f', 'g', 'h'];

我想获得这个数组所有可能的排列或组合，但不想从两个或多个子数组中两次使用相同的值。因此，例如，结果 a d b e f 是可能的，但不是 a d a d f。

我已经尝试过基本的排列算法，但我不知道如何修改它来做我想做的事情。

这是我目前得到的:

function array_permutation(array $a){
    $count = array_map('count', $a);
    $finalSize = 1;

    foreach ($count as $val) {
        $finalSize *= $val;
    }

    $output = [];

    for ($i = 0; $i < $finalSize; $i++) {
        $output[$i] = [];
        for ($c = 0; $c < count($a); $c++) {
            $index = ($i + $finalSize) % $count[$c];
            array_push($output[$i], $a[$c][$index]);
        }
    }
    return $output;
}

Answer 1

一个非常简单的方法是简单的循环:

function decartProductExclusive($one, $two)
{
   $result = [];
   for($i=0; $i<count($one); $i++)
   {
      for($j=0; $j<count($two); $j++)
      {
         if(!count(array_intersect((array)$one[$i], (array)$two[$j])))
         {
            $result[]=array_merge((array)$one[$i], (array)$two[$j]);
         }
      }
   }
   return $result;
}

function createAssociation()
{
   $args   = func_get_args();
   if(!count($args))
   {
      return [];
   }
   $result = array_shift($args);
   while($array=array_shift($args))
   {
      $result=decartProductExclusive($result, $array);
   }
   return $result;
}

$i[0] = ['a', 'b', 'c'];
$i[1] = ['d', 'e'];
$i[2] = ['a', 'b', 'c'];
$i[3] = ['d', 'e'];
$i[4] = ['f', 'g', 'h'];

$result = call_user_func_array('createAssociation', $i);

(检查 fiddle)您的问题是关于评估 Cartesian product ，但有条件，元组不能包含重复元素。但是，可以在不评估每次迭代中的交集的情况下满足此条件(这将是一种矫枉过正)。相反，您可以使用 array_unique() 过滤结果数组，如 this fiddle 。