受限制的笛卡尔积计算 - PHP

Question

编辑1 - 自发布以来我了解到底层问题是关于如何找到CARTESIAN PRODUCT(现在去谷歌),但不仅因为我不想要每一个烫发,我想找到使用相同子阵列的笛卡儿产品密钥永远不会超过一次,而我的"额外"问题则更多地是关于如何最大限度地减少笛卡尔产品所需的工作量(接受小错误率,我不得不说) -

想象一下......我有四个厨师和四个食谱,每个厨师都有每个食谱的分数,今天我希望每个厨师做一道菜(但不应该做两次菜),决定应该基于最好的所有四个(最高总分)排列(所以也许一个厨师不会使他个人最好).

我已经将数据放入多维数组中

 array(
   array (1,2,3,4),
   array (35,0,0,0),
   array (36,33,1,1),
   array (20,20,5,3)
 )

• 它在每个子数组中具有与子数组相同数量的值对(如果有帮助的话)

• 实际上,子阵列的数量最多会达到8(因此最大烫数= 8!,大约40,000不是8 ^ 8,因为不允许使用许多组合)

• 如果有帮助,选择以这种格式存储数据是灵活的

我正在尝试创建第二个数组,根据KEYs输出子数组的最佳(即最高值)可能组合,其中每个子数组只能使用一个子数组

- 这里每个子阵列[0] [1] [2] [3]每个排列使用一次,每个子阵列键[0] [1] [2] [3]每次使用一次,在我的实际问题中我正在使用相关的数组,但这对于这个问题来说是额外的.--

所以这个例子会创建一个像newArray(35,33,5,4)这样的数组//注意没有使用[2] [0]

理所当然我宁愿不生产所有的烫发,而是,SOMEHOW,丢弃许多显然不是最合适的组合.

有关如何开始的任何想法？我会接受伪代码.

有关笛卡尔积的SO的示例,请参阅PHP 2D阵列输出所有组合

编辑2了解更多关于使笛卡尔积更有效的信息,也许为什么它必须是特定于案例的,如果你想看看你是否可以偷工减料(有风险)高效的笛卡儿积算法

Answer 1

好的，这里有一个解决方案，可以让您找到一个厨师对一个食谱的最佳排列，并且没有厨师会工作两次，也没有食谱会做两次。

感谢 o'reilly 提供的计算数组 perm 的代码... http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

注意事项：

• 厨师的数量和菜谱的数量是相同的。

• 超过这里的 5 x 5 矩阵将会很快变得非常大。（参见即将发布的第 2 部分）

逻辑： 数组的排列分配一个位置以及只是被包含（即组合的作用），那么为什么不将这样一个数组的每个键分配给一个食谱，排列保证不会重复烹饪并且键保证菜谱不重复。

如果我的想法或代码有改进或错误，请告诉我，但就是这样！

<?php

function pc_next_permutation($p, $size) {
//this is from http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}
$cooks[441] = array(340=>5,342=>43,343=>50,344=>9,345=>0);
$cooks[442] = array(340=>5,342=>-33,343=>-30,344=>29,345=>0);
$cooks[443] = array(340=>5,342=>3,343=>0,344=>9,345=>10,);                     
$cooks[444] = array(340=>25,342=>23,343=>20,344=>19,345=>20,); 
$cooks[445] = array(340=>27,342=>27,343=>26,344=>39,345=>50,); 

//a consideration: this solution requires that the number of cooks equal the number of recipes
foreach ($cooks as $cooksCode => $cooksProfile){
        $arrayOfCooks[]=$cooksCode;
        $arrayOfRecipes = (array_keys($cooksProfile));
}
echo "<br/> here is the array of the different cooks<br/>";
print_r($arrayOfCooks);
echo "<br/> here is the array of the different recipes<br/>";
print_r($arrayOfRecipes);

$set = $arrayOfCooks;
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);
echo "<br/> here are all the permutations of the cooks<br/>";
print_r($perms);

$bestCombo = 0;
foreach($perms as $perm){
    $thisScore =0;
        foreach($perm as $key =>$cook){
        $recipe= $arrayOfRecipes[$key];
        $cookScore =$cooks[$cook][$recipe];
        $thisScore = $thisScore+$cookScore;
        }
    if ($thisScore>$bestCombo){
        $bestCombo=$thisScore;
        $bestArray= $perm;
    }
}



echo "<br/> here is the very best array<br/>";
print_r ($bestArray);
echo "<br/> best recipe assignment value is:".$bestCombo."<br/><br/>";  




?>