Testowałem jedynie 4 przypadki. Żeby sprawdzić, czy w ogóle przypisanie zadziałało poprawnie, musisz sprawdzić klucz w zwróconej tablicy not_possible_to_assign Tam będzie lista pól, do których nie udalo się przydzielić elementów. Jeśli funkcja wykonała się poprawnie, tablica będzie pusta.
Struktura danych może być czasami dziwna, bo to przepisany fragment mojego głównego algorytmu, więc nie wszystko poprawiałem i upraszczałem pod kątem tego zadania.
Idea działania polega na tym, że brane pod uwagę są dwa parametry: count i length. Ten drugi zawiera liczbę dostępnych elementów dla danego pola. Ten pierwszy oznacza odwrotność, czyli do ilu pól można przypisać dany element. Orginalnie algorytm umożliwia przypisanie wyłącznie jednego elementu do pola. Musiałem więc dodać zmianę, by uwzględnić ten warunek. $length[$key] = $row['length'] - $row['min_choice'] + 1; Nie testowałem tego koncepcyjnie, więc możliwe, że będą z tym jakieś problemy. W wersji pierwotnej działanie jest zawsze poprawne (przynajmniej nie znalazłem w nim żadnej dziury).
Dodatkowo wcześniej wystarczyła zwykła iteracja po dostępnych polach. Teraz musiałem dodać trochę brzydką sekwencje. Polega to na tym, że na początku następuje sortowanie w jakiej kolejności przypisać elementy do poszczególnych pól. O ile sprawdza się to orginalnie, to nie jestem pewien, czy w przypadku przypisywaniu kilku elementów do jednego pola, to sortowanie będzie działało optymalnie. Całkiem możliwe, że po przypisaniu 1 elementu do pola, należałoby powtórzyć sortowanie, gdyż parametry count i length pola się zmieniły i być może takie sekwencyjne przypisywanie się nie sprawdzi.
Dane wejściowe:
$elements = [
'A' => [2,],
'B' => [3, 5, 6, 7, 11],
'C' => [1, 2, 3, 4, 10],
'D' => [1, 8],
];
$params = [
'length' => [
'A' => 2,
'B' => 2,
'C' => 2,
'D' => 2
]
];
print_r(assign_elements_to_fields($elements, $params));
[chosen_elements] => Array
(
[C] => Array
(
[0] => 4
[1] => 10
)
[A] => Array
(
[0] => 2
)
[D] => Array
(
[0] => 8
[1] => 1
)
[B] => Array
(
[0] => 5
[1] => 6
)
)
[not_possible_to_assign] => Array
(
[0] => A
)
Jeśli potrzebujesz rozstrzygać remisy (wybór jakiegoś elementu do pola ze względu na jakąś jego wartość), musisz zmienić $chosen_element = array_pop($min_arrays); na jakąś swoją metodę, która z $min_arrays wybierze ten element, który aktualnie spełnia jakiś dodatkowy warunek
public function assign_elements_to_fields($possible_elements, $extra_params = []) {
$not_possible_to_assign = [];
$keys = array_keys($possible_elements);
$number_of_arrays = count($possible_elements) - 1;
$array_counts = array_fill(0, ($number_of_arrays + 1), [
'count' => 0,
'length' => 0,
'key' => -1,
'original_key' => -1,
]);
$possible_elements = array_values($possible_elements);
for ($i = 0; $i <= $number_of_arrays; $i++) {
$array_counts[$i]['length'] = count($possible_elements[$i]);
$array_counts[$i]['min_choice'] = isset($extra_params['length'][$keys[$i]]) ? $extra_params['length'][$keys[$i]] : 1;
$array_counts[$i]['key'] = $i;
$array_counts[$i]['original_key'] = $keys[$i];
$array_counts[$i]['current_available_elements'] = $possible_elements[$i];
for ($j = $i + 1; $j <= $number_of_arrays; $j++) {
$count = count(array_intersect($possible_elements[$i], $possible_elements[$j]));
$array_counts[$i]['count'] += $count;
$array_counts[$j]['count'] += $count;
}
}
$counts = $length = [];
foreach ($array_counts as $key => $row) {
$counts[$key] = $row['count'];
$length[$key] = $row['length'] - $row['min_choice'] + 1;
}
array_multisort($counts, SORT_DESC, $length, SORT_ASC, $array_counts);
$sorted_original_keys = $sorted_array = $current_available_elements = [];
foreach ($array_counts as $array) {
$sorted_array[] = $possible_elements[$array['key']];
$sorted_original_keys[] = $array['original_key'];
$current_available_elements[] = $array['current_available_elements'];
}
$all_possible_elements = array_reduce($possible_elements, 'array_merge', []);
$counted_possible_elements = array_count_values($all_possible_elements);
$arr_chosen_elements = [];
$sequence = [];
for ($i = 0; $i <= $number_of_arrays; $i++) {
for ($j = 0; $j < $array_counts[$i]['min_choice']; $j++) {
$sequence[] = $i;
}
}
for ($k = 0; $k < count($sequence); $k++) {
$i = $sequence[$k];
$allowed_numbers = [];
foreach ($sorted_array[$i] as $element) {
$allowed_numbers[$element] = $counted_possible_elements[$element];
}
if (count($allowed_numbers) == 0) {
$not_possible_to_assign[] = $sorted_original_keys[$i];
continue;
}
$chosen_element = NULL;
if (is_null($chosen_element)) {
// pobierz element, który występuje aktualnie najmniejszą liczbę razy
$min_counts = min($allowed_numbers);
// tablica zawiera te elementy, które występują taką samą liczbę razy
$min_arrays = array_keys($allowed_numbers, $min_counts);
if (count($min_arrays) == 1) { // jeśli jest tylko jeden element, to właściwie nie ma wyboru
$chosen_element = current($min_arrays);
} else { // jest kilka elementów do wyboru
$tmp = [];
$tmp[key($min_arrays)] = current($min_arrays);
$min_arrays = $tmp;
unset($tmp);
// i wybieramy ostatnia sale z listy lub dodajemy dodatkową funkcję tzw. tie-breaker
$chosen_element = array_pop($min_arrays);
}
}
$arr_chosen_elements[$i][] = $chosen_element;
$counted_possible_elements[$chosen_element]--;
for ($j = 0; $j <= $number_of_arrays; $j++) {
if (($key = array_search($chosen_element, $sorted_array[$j])) !== FALSE) {
unset($sorted_array[$j][$key]);
}
if (($key = array_search($chosen_element, $current_available_elements[$j])) !== FALSE) {
unset($current_available_elements[$j][$key]);
}
}
}
if (($number_of_chosen_elements = count($arr_chosen_elements) - 1) < $number_of_arrays) {
for ($i = $number_of_chosen_elements + 1; $i <= $number_of_arrays; $i++) {
unset($sorted_original_keys[$i]);
}
}
return [
'chosen_elements' => array_combine($sorted_original_keys, $arr_chosen_elements),
'not_possible_to_assign' => $not_possible_to_assign,
];
}