php - 受限笛卡尔积计算 - PHP

Question

编辑 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 输出子数组的最佳(即最高值)可能的组合，其中每个子数组中只能使用一个

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

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

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

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

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

编辑 2
有关使笛卡尔积更有效的更多信息，以及如果您想查看是否可以偷工减料(有风险) Efficient Cartesian Product algorithm 为什么必须针对具体情况

Answer 1

抱歉，但这将更多地是逻辑布局而不是代码......

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

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

asort() 每个数组，这样 $array[$cook_id] = array($lowest_scored_dish,...,$highest);

考虑一个特定厨师做一道菜的加权偏好是最好的菜和另一道菜的分数之间的差异。

作为一个非常简单的例子， cooking 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 道菜，然后继续 cooking '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);

再次开始 cooking 'a'，看到 0 是首选，但这次重量为 25。厨师 'b' 喜欢重量为 50，厨师 'c' 喜欢重量为 75。厨师 'c' 赢得第 0 道菜.

回到可用厨师列表，“a”更喜欢权重为 50 的 1，但“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 周期。