Как создать массив с равноудаленными элементами?

Question

[Денис]

Коллеги помогите придумать алгоритм.
Вроде все просто, но голова не варит;

Дано:

array(
A=3,
B=6,
C=9
)

Требуется сформировать массив из 18 элементов значения которых равны ключам входного массива,
их количество равно значению указанному в исходном массиве
Одинаковые значения находятся максимально далеко друг от друга

например ответ может быть таким:
CACBCBCBACBCBCACBC

UPDATE
Немного перефразирую задачу
Есть круг с 18 секторами
есть входные данные
красных = 3 сектора
желтых = 6 секторов
зеленых = 9 секторов
Нужно максимально равномерно разместить эти цветные сектора в круге.

UPDATE2
общая сумма значений исходного массива всегда равна 18. Минимальное значение входного элемента = 1
То-есть граничный случай входных данных
A=1
B=1
C=16

Заранее спасибо всем откликнувшимся

Comments

[Mercury13]

> Одинаковые значения находятся максимально далеко друг от друга
Критерий «качества», конечно, умозрительный.

[Денис]

немного дополнил сам вопрос

Answer 1

[volginn]

вот такая идея у меня
например нам надо разместить:
9-А
6-В
3-С
во первых мы создаем массив который будет ответом
во вторых мы создаем массив в котором будут храниться пустые индексы в выходном массиве

и теперь собственно само заполнение:
идем от тех элементов которых больше к тем которых меньше
1)вставляем 9-А
вычисляем коэффицент = количество свободных мест в выходном массиве/ количество вставляемых элементов
К=18/9=2

на данный момент у нас такая штука

выходной массив
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

массив пустых индексов в выходном
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
далее в 2,4,6,8,10,12,14,16,18 элементы вставляем А т.к. К=2

выходной массив
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
А А А А А А А А А

массив пустых индексов в выходном
1 2 3 4 5 6 7 8 9
1 3 5 7 9 11 13 15 17

ВТОРОЙ ШАГ
считаем для В
К=9/6=1,5
получаются индексы для равномерности распределения стоит округлять в меньшую сторону
1,5=1
3=3
4,5=4
6=6
7,5=7
9=9
получается что по этим индексам в массиве пустых мест лежат индексы тех мест куда надо вставить В
получаем выходной массив такого вида
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
В А А В А В А А В А В А А В А
пройдя еще раз для тройки тоже самое получим выходной массив
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
В А С А В А В А С А В А В А С А В А

Comments

[Денис]

Да так получается спасибо!

Answer 2

[Mercury13]

Неплохие результаты получились с одной из первых версий с простейшим патчем на повторы.

#include <iostream>

struct Sector
{
    char name;
    int total, counter, remainder;
    bool allowNearby;
};

enum { N = 3 };
Sector secs[] { { 'A', 3 }, { 'B', 6 }, { 'C', 30 } };

int main()
{
    int nTotal = 0;
    for (int i = 0; i < N; ++i) {
        Sector& sec = secs[i];
        nTotal += sec.total;
    }
    for (int i = 0; i < N; ++i) {
        Sector& sec = secs[i];
        sec.counter = sec.total;
        sec.remainder = sec.total;
        sec.allowNearby = (sec.total * 2 > nTotal);
    }

    Sector* repeatS = nullptr;
    for (int iSec = 0; iSec < nTotal; ++iSec) {
        Sector* bestS = nullptr;
        for (int i = 0; i < N; ++i) {
            Sector& sec = secs[i];
            if (sec.remainder != 0 && &sec != repeatS) {
                if (!bestS) {   // первый подходящий?
                    bestS = &sec;
                } else {    // лучше bestS?
                    if (sec.counter < bestS->counter
                            || (sec.counter == bestS->counter && sec.total > bestS->total))
                        bestS = &sec;
                }
            }
        }
        if (!bestS)     // так и не нашли, что брать — берём repeatS
            bestS = repeatS;

        // пересчитаем счётчик и остаток
        bestS->counter += nTotal * 2;
        --bestS->remainder;

        for (int i = 0; i < N; ++i) {
            Sector& sec = secs[i];
            sec.counter -= sec.total * 2;
        }
        repeatS = bestS->allowNearby ? nullptr : bestS;
        std::cout << bestS->name;
    }
    std::cout << std::endl;
}

Пишу на «си с крестами». Раз уж вы работаете на PHP, вместо указателей придётся держать «лучший индекс» и «последний индекс».

Принцип программы прост. Счётчики считают вниз с разной скоростью; чем чаще встречается сектор, тем быстрее. Приоритет взятия такой: не исчерпан → без повторов → у кого счётчик меньше → какой встречается чаще. Однако если какого-то сектора больше 50%, для него повторы вполне себе разрешены.

Comments

[Денис]

Действительно критерий качества пока несколько размытый, поэтому и задачу себе поставить толком не могу, соответственно и решить ее толком не могу.

Ваше решение малость недопонял. Можно вас попросить для тех "кто в танке" чуть чуть посильнее разжевать?

[Mercury13]

Если мы имеем дело не с линией, а с кругом, моё решение оптимально, к тому же очень красиво смотрится. И простое, как бревно.
Единственное, что — при равных fraction мы должны брать победителя строго определённым образом, первого или последнего. Но, думаю, это автоматически будет.

Интуитивно: смотрим, какой остался процент красных (жёлтых, зелёных) секторов. У кого он больше, тот сектор и ставим.

[Mercury13]

UPD: Я ошибся и при равных fraction брать тот, у кого больше total.

[Денис]

я так понимаю действуем так:
круг пустой
9 зеленых - ставим зеленый
8 зеленых - ставим зеленый
7 зеленых - ставим зеленый
...
или я вообще не врубаюсь :-)))))))))))))

[Mercury13]

Да, и всё равно я ошибся. Думаем дальше.

[Денис]

У меня была идея такая
вычисляем для каждого цвета шаг
и начинаем расставлять с наименьшего
в нашем случае красный

К=====К=====К=====
Затем следующий, начинаем ставить, но если место занято то сдвигаемся на шаг
КЖ==ЖК=Ж==КЖ==Ж==Ж
остальные заполняем зеленым
но получаются места где зеленый идет подряд. А не хотелось бы. Руками можно расставить более "рыхло"

[Mercury13]

Да уж, и этот алгоритм забуксовал, хотя не сразу.
Шаг 0: счётчики 5:11:17, доли 1,66−ε/3 : 1,83−ε/6 : 1,88−ε/9. Берём зелёный, З
Шаг 1: счётчики 5:11:15, доли 1,66−ε/3 : 1,83−ε/6 : 1,66−ε/9. Берём жёлтый, ЗЖ
Шаг 2: счётчики 5:9:15, доли 1,66−ε/3 : 1,5−ε/6 : 1,66−ε/9. Снова берём зелёный, ЗЖЗ
Шаг 3: счётчики 5:9:13, доли 1,66−ε/3 : 1,5−ε/6 : 1,44−ε/9. Берём красный, ЗЖЗК
Шаг 4: счётчики 4:9:15, доли 1−ε/3 : 1,5−ε/6 : 1,66−ε/9. Зелёный, ЗЖЗКЗ
Шаг 5: счётчики 4:9:13, доли 1−ε/3 : 1,5−ε/6 : 1,44−ε/9. Жёлтый, ЗЖЗКЗЖ
Шаг 6: счётчики 3:7:13, доли 1−ε/3 : 1,16−ε/6 : 1,44−ε/9. Зелёный, ЗЖЗКЗЖЗ
Шаг 7: счётчики 3:7:11, доли 1−ε/3 : 1,16−ε/6 : 1,22−ε/9. Зелёный, ЗЖЗКЗЖЗЗ!!!!!
Думаю дальше.

[Денис]

Mercury13: а дошагайте этот алгоритм дальше? до 18 шага. если там будет только 1 повтор то это может быть то что надо

[Mercury13]

Уже не то!

[Mercury13]

Подождите до ночи, меня задача заинтересовала, но вкалывать надо. Дома.

[Денис]

Mercury13: Спасибо за участие :-) буду очень ждать вашего варианта. пока накидаю еще одну идейку.

[Mercury13]

Прости, не смог — вынужден был сидеть до ночи на работе.

[Mercury13]

Написал кое-что, по старой привычке на «си с крестами».

[Mercury13]

Добавил небольшую перестраховку.