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

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

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

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

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

>它在每个子数组中具有与子数组相同数量的值对(如果有帮助的话)
>实际上,子阵列的数量最多会达到8(因此最大烫数= 8！,大约40,000不是8 ^ 8,因为不允许使用多种组合)
>如果有帮助,选择以这种格式存储数据是灵活的

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

– 这里每个子阵列[0] [1] [2] [3]每个排列使用一次
每个subarrayKey [0] [1] [2] [3]每个permutaion将使用一次,在我的实际问题中,我正在使用相关的数组,但这是这个问题的额外内容.–

因此,该示例将创建一个数组
newArray(35,4)//注意没有使用[2] [0]

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

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

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

编辑2
更多关于提高笛卡尔产品效率的更多信息,也许为什么如果你想看看是否可以偷工减料(具有风险),为什么它必须是特定的？Efficient Cartesian Product algorithm

我不太清楚阵列(1,4)是第一道菜还是第一道菜的得分,但是我可能会使用这样的阵列

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

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

考虑对特定厨师的加权偏好,使菜肴成为最佳菜肴与另一菜肴得分之间的差异.

作为一个非常简单的例子,烹饪a,b,c和菜肴0,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,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’开始,他喜欢在他的下一道菜中获得50分(重量)的菜0. Cook’b’也喜欢dih 0,但是在下一道菜中重量为0.因此,它很可能(虽然还不确定烹饪’a’应该制作菜0.

考虑保留菜0并继续烹调’b’.不包括菜0,烹饪’b’更喜欢菜1.没有其他厨师喜欢菜1,所以烹饪’b’被指定为菜1.

Cook’c’默认为2.

这是一个非常方便的例子,每个厨师都可以烹饪一些个人最大的东西,但我希望它能说明一些可以解决的问题.

让它不那么方便：

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

再次尝试烹饪’a’并看到0是首选,但这次重量为25. Cook’b’喜欢重量为50而烹饪’c’更喜欢重量为75. Cook’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’赢得1,体重149
‘d’胜2,因为’c’没有可用选项的偏好
‘c’得3分

得分：200 149 147 16 = 512

虽然这是一个很好的猜测,没有检查每个排列,但它可能是错误的.从这里开始,问：“如果一个厨师与其他任何一个厨师交易,那么总量会增加吗？”

答案是YES,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

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

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

如果它确实有效,并且你从正确的选择开始,上面的代码将只循环64次(8×8)8个厨师/菜.如果选择不正确并且第一个厨师有变化,那么它将达到72.如果第8个厨师有变化,则最多为128.这可能会多次循环,但我怀疑它会接近所有40k组合所需的CPU周期.

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!