php - 如何根据键可用性将所有输入值分配到数组中而不会发生冲突？

Question

我正在寻找槽填充技术。我有 8 个“插槽”表示为平面阵列。我还有一个多维数组，其中键是主题，值是包含索引元素(槽)的子数组。

多维数组 ( $emp ) 可能包含，例如，主题 Tamil可用于插槽 1 到 5，和/或 English仅在插槽 4、5 或 6 期间可用。提供的所有科目都将有一系列可用插槽 - 即使只有一个插槽可用。

主题可用性:

$emp = array(
    "tamil"   => array(1, 2, 3, 4, 5),
    "english" => array(4, 5, 6),
    "maths"   => array(1, 5, 8),
    "social"  => array(1, 2, 5),
    "pt"      => array(1),
    "hindi"   => array(3, 4, 7)
);

我需要在我的输出数组 ($sort) 中为以下主题分配确切的次数——同时遵守主题可用性并且不会遇到“插槽冲突”:

• 泰米尔语 2 次
• PT 1 次
• 数学 2 次
• 社交 1 次
• 印地语 1 次
• 英语 1 次

必须填满所有 8 个位置。所有科目都必须只出现一次，但泰米尔语和数学除外，它们必须恰好出现两次。

输出可能是:

$slot[3] = 'tamil',
$slot[7] = 'Hindi', 
$slot[6] = 'English',
$slot[1] = 'Pt',
$slot[5] = 'Maths',
$slot[8] = 'Maths',
$slot[4] = 'Tamil',
$slot[2] = 'Social'.

我曾尝试自己编写代码，但没有成功。

for ($i = 1; $i < 9; $i++) {
    $var = $subarray[$i];
    if (count($var) <= 1) { 
        $filledslots[$i] = $var[0];
    } else {
        $empty[$i] = '';
    }
}
$subjects = array_flat($subarray); 
$count_values = array(); 
$subjects = array_diff($subjects, $filledslots);
foreach ($subjects as $value) { 
   $count_values[$value] = 0; 
   foreach ($empty as $key => $val) {
       $res = $subarray[$key];
       if (in_array($value, $res)) {
           $count_values[$value] = $count_values[$value] + 1;
       }
   }
   if ($count_values[$value] == 1) {
       //$filledslots[1] = $count_values[$value];
       foreach ($empty as $key => $val) {
           $res = $subarray[$key]; 
           if (in_array($value, $res)) {
               $filledslots[$key] = $value;
           }
       }
   }
}
print_r(($filledslots)); 

Answer 1

这是一个有效的递归技术，它将返回第一个符合条件的数据集。

它的工作原理是从“required subjects”数组和“available slots”数组中删除元素，同时向“filled slots”数组添加元素。

使用 array_replace() 将限定值插入递归调用中传递的第三个参数，可防止破坏 $filledSlots 变量的状态，该变量将继续由 foreach 循环使用。

函数:(Demo)

function fillSlots($requiredSubjects, $availableSlots, $filledSlots = []) {
    if (!$requiredSubjects) {
        ksort($filledSlots);
        return $filledSlots;
    }
    foreach ($requiredSubjects as $rIndex => $subject) {
        foreach ($availableSlots[$subject] as $sIndex => $slot) {
            if (!isset($filledSlots[$slot])) {
                unset($requiredSubjects[$rIndex], $availableSlots[$subject][$sIndex]);
                $result = fillSlots(
                    $requiredSubjects,
                    $availableSlots,
                    array_replace($filledSlots, [$slot => $subject])
                );
                if ($result) {
                    return $result;
                }
            }
        }
    }
}

输入变量:

$subjectSlots = [
    "tamil"   => [1, 2, 3, 4, 5],
    "english" => [4, 5, 6],
    "maths"   => [1, 5, 8],
    "social"  => [1, 2, 5],
    "pt"      => [1],
    "hindi"   => [3, 4, 7]
];
$requiredSubjects = ['tamil', 'tamil', 'pt', 'maths', 'maths', 'social', 'hindi', 'english'];

---

为了让函数的执行速度快上千倍(出于好奇，我进行了基准测试)，准备输入数据，以便首先迭代槽较少的主题。

执行前排序:( See the effect )

usort($requiredSubjects, function($a, $b) use ($subjectSlots) {
    return $subjectSlots[$a] <=> $subjectSlots[$b];  // sort by length, then by values
});

---

初始调用:

var_export(fillSlots($requiredSubjects, $subjectSlots));

输出:

array (
  1 => 'pt',
  2 => 'social',
  3 => 'tamil',
  4 => 'tamil',
  5 => 'maths',
  6 => 'english',
  7 => 'hindi',
  8 => 'maths',
)