Pytanie o algorytm 2

0

Dzień dobry,

Mamy np. pole A, pole B, pole C (liczba pól zmienna). W każdym polu ma znajdować się po 2 elementy (dla każdego pola wartość zmienna).

Lista elementów:
element nr 1 (Cecha elementu: może znajdować się w polu A, B lub C)
element nr 2 (Cecha elementu: może znajdować się w polu A, B lub C)
element nr 3 (Cecha elementu: może znajdować się w polu A lub B)
element nr 4 (Cecha elementu: może znajdować się w polu A lub B)
element nr 5 (Cecha elementu: może znajdować się w polu C)
element nr 6 (Cecha elementu: może znajdować się w polu C)

Każdy z elementów może znajdować się tylko raz w danym polu. Liczba elementów jak i ich cechy to wartości zmienne.

Chodzi mi o utworzenie algorytmu, który wstawi elementy w pola bazujących na zmiennych: ilość pól, ilość wymaganych elementów dla poszczególnych pól, ilość dostępnych elementów, cechy tych elementów. Wszelkie sugestie mile widziane jak do tego tematu podejść. Jeżeli ktoś chciałby się tego podjąć odpłatnie to również Proszę o kontakt.

0

Używam czegoś podobnego dla siebie tylko z kluczowym założeniem, że każde pole może mieć tylko i wyłącznie 1 element.
W jakim języku piszesz? Mogę później sprawdzić, czy to zadziała przy Twoich założeniach.

0

Byłoby super. W JS.

1

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,
        ];
    }
0

Dzięki wielkie za pomoc :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1