Подтвердить что ты не робот

Алгоритм разделения элементов того же типа

У меня есть список элементов, каждый из которых идентифицирован с типом, мне нужно переупорядочить список до максимизировать минимальное расстояние между элементами одного и того же типа.

Набор мал (от 10 до 30 штук), поэтому производительность не очень важна.

Нет ограничений на количество элементов на тип или количество типов, данные можно считать случайными.

Например, если у меня есть список:

  • 5 элементов A
  • 3 элемента B
  • 2 элемента C
  • 2 элемента D
  • 1 элемент E
  • 1 элемент F

Я хотел бы создать что-то вроде: A, B, C, A, D, F, B, A, E, C, A, D, B, A

  • A имеет как минимум 2 элемента между вхождениями
  • B имеет не менее 4 элементов между вхождениями
  • C имеет 6 элементов между вхождениями
  • D имеет 6 элементов между вхождениями

Есть ли алгоритм для достижения этого?

-Обновление -

После обмена некоторыми комментариями я пришел к определению вторичной цели:

  • главная цель: максимизировать минимальное расстояние между элементами одного и того же типа, учитывая только тип с меньшим расстоянием.
  • вторичная цель: максимизировать минимальное расстояние между элементами на каждом типе. IE: если комбинация увеличивает минимальное расстояние определенного типа без уменьшения другого, выберите его.

-Update 2 -

Об ответах. Было много полезных ответов, хотя ни одно из них не является решением для обоих целей, особенно второе, что сложно.

Некоторые мысли об ответах:

  • PengOne: Звучит неплохо, хотя и не обеспечивает конкретной реализации, и не всегда приводит к лучшему результату в соответствии со второй целью.
  • Евгений Клюев: Обеспечивает конкретную реализацию главной цели, но это не приводит к лучшему результату в соответствии с вторичной целью.
  • tobias_k: Мне понравился случайный подход, это не всегда приводит к лучшему результату, но это хорошее приближение и экономичность.

Я попробовал комбинацию Evgeny Kluev, backtracking и tobias_k formula, но для получения результата потребовалось слишком много времени.

Наконец, по крайней мере, для моей проблемы, я считал, что tobias_k является наиболее адекватным алгоритмом, за его простоту и хорошие результаты своевременно. Вероятно, его можно было бы улучшить с помощью имитационного отжига.

4b9b3361

ОТВЕТЫ

Ответ 1

Это звучало как интересная проблема, поэтому я просто попробовал. Здесь мой супер-упрощенный рандомизированный подход, выполненный в Python:

def optimize(items, quality_function, stop=1000):
    no_improvement = 0
    best = 0
    while no_improvement < stop:
        i = random.randint(0, len(items)-1)
        j = random.randint(0, len(items)-1)
        copy = items[::]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality_function(copy)
        if q > best:
            items, best = copy, q
            no_improvement = 0
        else:
            no_improvement += 1
    return items

Как уже обсуждалось в комментариях, очень сложной частью является функция качества, переданная в качестве параметра оптимизатору. После некоторых попыток я придумал тот, который почти всегда дает оптимальные результаты. Спасибо пмолери, за то, что он указал, как сделать это намного эффективнее.

def quality_maxmindist(items):
    s = 0
    for item in set(items):
        indcs = [i for i in range(len(items)) if items[i] == item]
        if len(indcs) > 1:
            s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))
    return 1./s

И вот какой-то случайный результат:

>>> print optimize(items, quality_maxmindist)
['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']

Обратите внимание, что, передавая другую функцию качества, один и тот же оптимизатор может использоваться для различных задач перераспределения списков, например. как (довольно глупый) рандомизированный сортировщик.

Ответ 2

Во-первых, у вас пока еще нет четко определенной проблемы оптимизации. Если вы хотите максимизировать минимальное расстояние между двумя элементами того же типа, которые хорошо определены. Если вы хотите максимизировать минимальное расстояние между двумя A и между двумя B и... и между двумя Z, то это не определено. Как бы вы сравнили два решения:

  • A по крайней мере 4 друг от друга, B по меньшей мере 4 друг от друга, и C не менее чем на 2 части.
  • A по крайней мере 3 друг от друга, B как минимум 3 друг от друга, и C, по крайней мере, на 4 части.

Вам нужна четкая мера "хорошего" (или, точнее, "лучше" ). На данный момент я предполагаю, что эта мера: максимизировать минимальное расстояние между любыми двумя из того же элемента.

Здесь алгоритм, который достигает минимального расстояния ceiling(N/n(A)), где N - общее количество элементов, а n(A) - количество элементов экземпляра A, считая, что A является самым многочисленным.

  • Закажите типы элементов A1, A2, ... , Ak где n(Ai) >= n(A{i+1}).
  • Инициализировать список L пустым.
  • Для j от k до 1 распределите элементы типа Ak как можно более равномерно в L.

Пример. Учитывая распределение в вопросе, алгоритм производит:

F
E, F
D, E, D, F
D, C, E, D, C, F
B, D, C, E, B, D, C, F, B
A, B, D, A, C, E, A, B, D, A, C, F, A, B

Ответ 3

Вот алгоритм, который максимизирует минимальное расстояние между элементами одного и того же типа и ничего не делает дальше. В качестве примера используется следующий список:

AAAAA BBBBB CCCC DDDD EEEE FFF GG
  • Элемент сортировки сортирует по количеству элементов каждого типа в порядке убывания. На самом деле в голову списка должны быть помещены только самые большие множества (A и B), а также те наборы элементов, которые имеют один элемент меньше (C и D и E). Другие наборы могут быть несортированы.
  • зарезервируйте последние позиции в массиве для одного элемента из каждого из самых больших наборов, разделите оставшийся массив равномерно между остальными элементами S-1 из самых больших наборов. Это дает оптимальное расстояние: K = (N - R)/(S - 1). Представить целевой массив как 2D-матрицу с K столбцами и L = N/K полными строками (и, возможно, одной частичной строкой с элементами N% K). Например, множества R = 2, S = 5, N = 27, K = 6, L = 4.
  • Если матрица имеет S - 1 полные строки, заполните первые R столбцов этой матрицы элементами самых больших множеств (A и B), иначе последовательно заполняйте все столбцы, начиная с последнего.

В нашем примере это дает:

AB....
AB....
AB....
AB....
AB.

Если мы попытаемся заполнить остальные столбцы другими наборами в том же порядке, возникает проблема:

ABCDE.
ABCDE.
ABCDE.
ABCE..
ABD

Последний "E" - всего 5 позиций, кроме первого "E".

  • Последовательно заполните все столбцы, начиная с последнего.

В нашем примере это дает:

ABFEDC
ABFEDC
ABFEDC
ABGEDC
ABG

Возвращаясь к линейному массиву, имеем:

ABFEDCABFEDCABFEDCABGEDCABG

Вот попытка использовать симулированный отжиг для этой проблемы (источники C): http://ideone.com/OGkkc.

Ответ 4

Я считаю, что вы могли видеть свою проблему как кучу частиц, которые физически отталкивают друг друга. Вы можете переходить в "стабильную" ситуацию.

Основной псевдокод:

force( x, y ) = 0 if x.type==y.type
                1/distance(x,y) otherwise 

nextposition( x, force ) = coined?(x) => same
                           else => x + force

notconverged(row,newrow) = // simplistically
   row!=newrow

row=[a,b,a,b,b,b,a,e]; 
newrow=nextposition(row);
while( notconverged(row,newrow) )
   newrow=nextposition(row);

Я не знаю, сходится ли он, но это идея:)

Ответ 5

Я уверен, что может быть более эффективное решение, но здесь есть одна возможность для вас:

Во-первых, обратите внимание, что очень легко найти порядок, который создает минимальное расстояние между элементами одного и того же типа 1. Просто используйте произвольное упорядочение, а MDBIOST будет не менее 1, если не более.

Итак, начните с предположения, что MDBIOST будет 2. Сделайте рекурсивный поиск пространства возможных упорядочений, исходя из предположения, что MDBIOST будет равно 2. Существует ряд условий, которые вы можете использовать для обрезки ветвей из этого поиска. Завершите поиск, если вы найдете заказ, который работает.

Если вы нашли тот, который работает, повторите попытку, предположив, что MDBIOST будет 3. Затем 4... и так далее, пока поиск не завершится с ошибкой.

ОБНОВЛЕНИЕ: На самом деле было бы лучше начать с большого числа, потому что это еще больше ограничит возможные варианты. Затем постепенно уменьшайте число, пока не найдете порядок, который работает.

Ответ 6

Вот еще один подход.

Если каждый элемент должен храниться как минимум в k местах от каждого другого элемента того же типа, то записывайте элементы слева направо, отслеживая количество элементов, оставшихся от каждого типа. В каждой точке положите элемент с наибольшим числом, оставшимся, что вы можете законно подавить.

Это будет работать для N элементов, если не более чем ceil (N/k) элементов одного типа, так как он сохранит это свойство - после того, как вы поместили k элементов, у нас осталось меньше предметов, и мы поставили на по меньшей мере один из каждого типа, который начинался с элементов ceil (N/k) этого типа.

Учитывая сцепление смешанных предметов, вы можете выработать самый большой k, который вы можете поддержать, а затем выложить элементы для решения для этого k.