5

编辑1-自从发布以来,我了解到基本问题是关于如何找到笛卡尔积(现在去谷歌),但不仅因为我不想要每个烫发,我还想找到使用相同子数组的笛卡尔积每个排列的关键不超过一次,我的“额外”问题更多是关于如何最小化笛卡尔积所需的工作量(我不得不说,接受一个小的错误率) -

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

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

 array(
   array (1,2,3,4),
   array (35,0,0,0),
   array (36,33,1,1),
   array (20,20,5,3)
 )
  • 它在每个子数组中的值对数量与子数组的数量相同(如果有帮助的话)

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

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

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

- 所以这里每个 subarray[0][1][2][3] 将被使用一次 permutation 并且每个 subarrayKey [0][1][2][3] 将在 permutaion 中使用一次,在我的实际问题中我正在使用关联的数组,但这对于这个问题来说是额外的。--

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

理想情况下,我宁愿不生产所有烫发,而是以某种方式丢弃许多显然不是最合适的组合。

关于如何开始的任何想法?我会接受伪代码。

有关笛卡尔积的 SO 示例,请参阅PHP 2D Array output all combination

编辑 2 以了解更多关于使笛卡尔积更高效的信息,以及为什么如果您想查看是否可以偷工减料(有风险)必须针对具体情况的原因高效笛卡尔积算法

4

4 回答 4

2

抱歉,但这将更像是逻辑布局而不是代码......

我不太清楚 array(1,2,3,4) 是第一道菜还是第一个厨师的分数,但我可能会使用这样的数组

$array[$cook_id][$dish_number] = $score;

asort() 每个数组,使得 $array[$cook_id] = array($lowest_scored_dish,...,$highest);

考虑一个特定厨师做一道菜的加权偏好是最好菜与另一道菜的得分之差。

作为一个非常简单的示例,烹饪 a、b、c 和菜肴 0、1、2

$array['a'] = array(0=>100, 1=>50, 2=>0); // cook a prefers 0 over 1 with weight 50, over 2 with weight 100
$array['b'] = array(0=>100, 1=>100, 2=>50); // cook b prefers 0,1 over 2 with weight 50
$array['c'] = array(0=>50, 1=>50, 2=>100); // cook c prefers 2 with weight 50

asort() 之后: $array['a'] = array(0=>100, 1=>50, 2=>0); $array['b'] = array(0=>100, 1=>100, 2=>50); $array['c'] = array(2=>100, 0=>50, 1=>50);

从厨师 'a' 开始,他更喜欢菜 0,而不是下一个最好的菜 50 分(重量)。Cook 'b' 也更喜欢 dih 0,但下一道菜的权重为 0。因此它很可能(虽然还不确定厨师'a'应该做菜0。

考虑保留第 0 道菜,然后继续烹饪“b”。排除菜 0,厨师“b”更喜欢菜 1。没有其他厨师喜欢菜 1,因此厨师“b”被分配菜 1。

Cook 'c' 默认获得第 2 道菜。

这是一个非常方便的例子,每个厨师都可以做一些个人最大的食物,但我希望它能够说明一些可行的逻辑。

让我们让它不那么方便:

$array['a'] = array(0=>75, 1=>50, 2=>0);
$array['b'] = array(0=>100, 1=>50, 2=>50);
$array['c'] = array(0=>100, 1=>25, 2=>25);

再次从厨师“a”开始,看到首选 0,但这次重量为 25。厨师“b”更喜欢重量为 50,厨师“c”更喜欢重量为 75。厨师“c”赢得第 0 道菜.

回到可用厨师列表,'a' 喜欢 1 的重量为 50,但 'b' 喜欢它的重量为 0。'a' 得到菜 1,'b' 得到菜 2。

这仍然不能解决所有的复杂问题,但这是朝着正确方向迈出的一步。有时对第一次烹饪/菜肴组合所做的假设是错误的。

不太方便:

$array['a'] = array(0=>200, 1=>148, 2=>148, 3=>0);
$array['b'] = array(0=>200, 1=>149, 2=>0, 3=>0);
$array['c'] = array(0=>200, 1=>150, 2=>147, 3=>147);
$array['d'] = array(0=>69, 1=>18, 2=>16, 3=>15);

'a' 得到 0,因为这是最大值,没有其他人更喜欢 0 的权重更高 'b' 以 149 的权重赢得 1 'd' 赢得 2,因为 'c' 在可用选项中没有偏好' c' 得到 3

得分:200+149+147+16 = 512

虽然这是在没有检查每个排列的情况下收集的一个很好的猜测,但它可能是错误的。从这里开始,问:“如果一位厨师与另一位厨师交易,总数会增加吗?”

答案是肯定的,a(0)+d(2) = 200+16 = 216,但是 a(2)+d(0) = 148+69 = 217。

我将留给您使用加权方法编写“最佳猜测”的代码,但在那之后,这对您来说是一个好的开始:

// a totally uneducated guess...
$picks = array(0=>'a', 1=>'b', 2=>'c', 3=>'d');

do {
    $best_change = false;
    $best_change_weight = 0;
    foreach ($picks as $dish1 => $cook1) {
        foreach ($picks as $dish2 => $cook2) {
            if (($array[$cook1][$dish1] + $array[$cook2][$dish2]) <
                ($array[$cook1][$dish2] + $array[$cook2][$dish1]))
            {
                $old_score = $array[$cook1][$dish1] + $array[$cook2][$dish2];
                $new_score = $array[$cook1][$dish2] + $array[$cook2][$dish1];
                if (($new_score - $old_score) > $best_change_weight) {
                    $best_change_weight = $new_score - $old_score;
                    $best_change = $dish2;
                }
            }
        }
        if ($best_change !== false) {
            $cook2 = $picks[$best_change];
            $picks[$dish1] = $cook2;
            $picks[$dish2] = $cook1;
            break;
        }
    }
} while ($best_change !== false);

我找不到反例来证明这不起作用,但我怀疑 ($array[$cook1][$dish1] + $array[$cook2][$dish2]) = = ($array[$cook1][$dish2] + $array[$cook2][$dish1])

也许其他人会跟进这个“如果?”的答案。

给定这个矩阵,括号中的项目是“选择”

[a1]   a2   a3
 b1   [b2]  b3
 c1    c2  [c3]

如果 a1 + b2 == a2 + b1,那么 'a' 和 'b' 不会换菜。我不确定 100% 的情况是是否存在一个矩阵,这样这是一个更好的选择:

 a1   [a2]   a3
 b1    b2   [b3]
[c1]   c2    c3

从第一个状态到第二个状态需要两个开关,第一个似乎是任意的,因为它不会改变总数。但是,只有通过这种任意更改才能进行最后一次切换。

我试图找到一个 3x3 的例子,这样基于我上面写的“加权偏好”模型,第一个将被选择,但真正的最佳选择由第二个给出。我找不到一个例子,但这并不意味着它不存在。我现在不想做更多的矩阵代数,但也许有人会从我离开的地方继续。哎呀,也许这种情况不存在,但我想我应该指出这个问题。

如果它确实有效并且你从正确的选择开始,上面的代码将只循环 64 次 (8x8) 用于 8 个厨师/菜肴。如果选择不正确并且第一个厨师有变化,那么它将上升到 72。如果第 8 个厨师有变化,则上升到 128。do-while 可能会循环几次,但我怀疑它将接近对所有 40k 组合求和所需的 CPU 周期。

于 2013-04-26T17:12:39.797 回答
1

我可能有这个算法的起点,该算法试图根据他们的最高分数与分数总和的比率来选择厨师(因此试图选择在一个食谱上非常擅长但在其余食谱上做得不好的厨师那个食谱)

$cooks = array(
    array(1,2,3,4),
    array(35,0,0,0),
    array(36,33,1,1),
    array(20,20,5,3)
);
$results = array();

while (count($cooks)) {
    $curResult = array(
        'cookId' => -1,
        'recipe' => -1,
        'score'  => -1,
        'ratio'  => -1
    );
    foreach ($cooks as $cookId => $scores) {
        $max = max($scores);
        $ratio = $max / array_sum($scores);
        if ($ratio > $curResult['ratio']) {
            $curResult['cookId'] = $cookId;
            $curResult['ratio']  = $ratio;
            foreach ($scores as $recipe => $score) {
                if ($score == $max) {
                    $curResult['recipe'] = $recipe;
                    $curResult['score']  = $score;
                }
            }
        }
    }

    $results[$curResult['recipe']] = $curResult['score'];
    unset($cooks[$curResult['cookId']]);
    foreach ($cooks as &$cook) {
        unset($cook[$curResult['recipe']]);
    }
}

对于提供的数据集,它确实找到了似乎是最佳答案 (35,33,5,4)。但是,它仍然不完美,例如,使用数组:

$cooks = array(
    array(1,2,3,4),
    array(35,0,33,0),
    array(36,33,1,1),
    array(20,20,5,3)
);

理想的答案是 (20,33,33,4),但是这个算法会返回 (35,33,5,4)。

但是由于问题是询问从哪里开始的想法,我想这至少可能足以从以下内容开始:P

于 2013-04-26T10:22:10.250 回答
0

尝试这个

$mainArr = array(
   array (1,2,3,4) ,
   array (35,0,0,0) ,
   array (36,33,1,1) ,
   array (20,20,5,3) 
 );
$i = 0;
foreach( $mainArr as $subArray )
{
    foreach( $subArray as $key => $value)
    {
        $newArr[$key][$i]=$value;
        $i++;   
    }
}
$finalArr = array();
foreach( $newArr as $newSubArray )
{
    $finalArr[] = max($newSubArray);    
}
print_r( $finalArr );
于 2013-04-26T08:39:33.050 回答
0

好的,这是一个解决方案,可让您找到一个厨师到一个食谱的最佳排列,没有厨师工作两次,也没有食谱做两次。

感谢计算数组 perm 的代码转到 o'reilly... 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/>";  




?>
于 2013-04-28T16:42:38.630 回答