Как максимизировать расстояние в круговом списке для однотипных объектов? - PullRequest
Новая
       27

Как максимизировать расстояние в круговом списке для однотипных объектов?

0 голосов
/ 07 февраля 2019

Существует N массивов, содержащих одинаковые объекты.{A, A, A, A} {B, B, B, B} {C, C} {D} {E} {F}.Идея состоит в том, чтобы поместить их в круговой массив, максимизируя расстояние между любыми двумя одинаковыми объектами внутри него.Например, в этом случае я ожидаю, что результирующий массив будет {A, B, C, F, A, B, E, A, B, C, A, B, D}.Любые элементы массива из одного элемента являются взаимозаменяемыми и обеспечивают дополнительное заполнение, поскольку из-за круглого массива расстояние всегда будет Array.Length -1

Текущая реализация алгоритма довольно проста.Я строю новый 2-мерный массив с длиной оси Y самого длинного исходного массива, а ось X - это просто количество массивов (бесконечно, чтобы упростить его).

Новый массив заполняется таким образом:
{A, B, C, D}
{A, B, C, 0}
{A, B, E, 0}
{A, B, F, 0}
0 - ноль
Идя сверху вниз, слева направо, я заполняю сетку, размещая наибольшее количество наименьшее.Затем, читая слева направо, сверху вниз и игнорируя нулевые значения, я получаю полу-правильное решение проблемы.Таким образом, решение является {A, B, C, D, A, B, C, A, B, E, A, B, F} Единственная проблема, с которой я сталкиваюсь, состоит в том, что элементы C "слишком близки" к каждомуДругой.Их текущий счет 3-8 вместо 5-6 или 6-5, что было бы более «просто».

Другое общее решение состояло в том, чтобы сформировать смешанный массив {A, B, C, D, E, F, A, B, C, A, B, A, B}, затем "Bubble sort" вокруг любых дублирующихся значений, но решение, похоже, имело слишком много краевых случаев.(Бесконечный цикл, если какой-либо один элемент доминирует в массиве)

Кажется, должен быть какой-то очевидный простой алгоритм для максимизации распределения, но я нигде не мог найти такую ​​вещь.У кого-нибудь есть решение этой проблемы?Можно ли вообще это решить?

Редактировать:
Еще одно проверенное решение состояло в том, чтобы одинаково рассчитать позиции, в которые должен быть помещен объект. Пример.
{A, A, A, A} -> 0/4 1/4 2/4 3/4
{B, B, B} -> 0/3 1/3 2/3 и т. Д.... Также добавляем небольшой сдвиг для каждого следующего значения, чтобы избежать совпадений.

Проблема возникает с начальными данными {A, A, A, A, B, B, B, C, C, C}, они преобразуются в {A, B, C, A, B, C, A, B, C, A}, который сдвигает значение A без заполнения до следующего объекта.

Редактировать 2:
Добавление расчета пригодности при формировании списка.Это более или менее грубая сила вместо элегантного алгоритма.Это всегда обеспечивает наилучшее возможное решение.

Чем ниже значение, тем лучше результат, наилучшая возможная пригодность равна 0, но часто это невозможно. 

#include <iostream>
#include <vector>
#include <algorithm>

float CalculateFitness(std::vector<char>& data, char tst, int count);

int main()
{
    std::vector<char> a = { 'A', 'A', 'A' };
    std::vector<char> b = { 'B', 'B' };
    std::vector<char> c = { 'C', 'C' };

    std::vector<char> data;
    data.insert(data.end(), a.begin(), a.end());
    data.insert(data.end(), b.begin(), b.end());
    data.insert(data.end(), c.begin(), c.end());

    do
    {
        for (auto val : data)
            std::cout << val;
        std::cout << ' ' << CalculateFitness(data, a[0], a.size()) + CalculateFitness(data, b[0], b.size()) + CalculateFitness(data, c[0], c.size()) << '\n';

    } while (std::next_permutation(data.begin(), data.end()));
}

float CalculateFitness(std::vector<char>& data, char tst, int count)
{
    const float mathematicallyJust = static_cast<float>(data.size()) / count;
    float result = 0;
    int lastPos = -1;
    for (auto i = 0; i <= data.size(); i++)
    {
        if (data[i % data.size()] == tst)
        {
            if (lastPos == -1)
            {
                lastPos = i;
                continue;
            }
            result += abs(mathematicallyJust - abs(lastPos - i));
            lastPos = i;
        }
    }
    return result;
}
...