Простые перестановки

(Задача о пересадках кустов)

Ко мне обратились со следующей несложной прикладной задачей: имеется набор высаженных в ряд кустов двух видов (кусты одного вида обозначены x, а другого — o):

x|x|x|x|x|x|x|x|x|x|o|o|o|o|o

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

o|o|x|o|o|x|o|o|x|o|o|x|o|o|x

Поскольку выполнение таких пересадок в реальности трудозатратно, то желательно найти минимальное  их количество, приводящее к желаемому результату.

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

Для формирования плана перестановок была написана следующая простая программа, входными данными которой являются \(n\) и \(m\) — количества образцов одного и другого вида соответственно.

n, m =10, 5

array = 'o' * n + 'x' * m

s = int((n + m) / float(min(m, n)))

print '===================== Input array==================='
print '|'.join(array[:])
print '===================================================='

def permute(n, m):
    assert n >= m, "n should be greater or equal m"
    marked = filter(lambda x: (x + 1) % s == 0, range(n+m))
    cm = m - len(filter(lambda x: (x + 1) > n, marked))
    tomove = filter(lambda x: (x + 1) > n,
                             filter(lambda x: (x + 1) % s > 0, range(n+m)))
    print 'The number of replacements (min): %s' % cm
    leave = filter(lambda x: (x+1) <= n, marked)[:-cm]
    res = [x for x in array]  # ['o'] * (n + m)
    for i in filter(lambda x: (x + 1) <= n, marked):
        if i  not in leave:
            res[i] = 'x'
            try:
                res[tomove.pop()] = 'o'
            except IndexError:
                pass
            finally:
                print '|'.join(res)
    return res

res = permute(n, m)

print '===================== Replacement plan ============='
print '|'.join(res)
print '===================================================='

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

Алгоритм формирования плана перестановок следующий:

  1. Определяется через какое число позиций должны следовать представители вида, который представлен меньшим числом образцов (это параметр \(s\), строка 5)
  2. Формируется набор позиций, в которые должны быть помещены виды с меньшим числом образцов (параметр marked строка 13)
  3. Определяется минимальное число необходимых перестановок — это количество малочисленных образцов за вычетом тех позиций в массиве marked, которые уже выпадают на малочисленные образцы (строка 14)
  4. Определяются позиции тех образцов, из числа малочисленных, которые необходимо переместить (строка 15); эти позции используются далее в цикле формирования плана перестановок
  5. Определяются позции (для вида, который представлен большим числом образцов),  которые останутся нетронутыми по причине отсутствия необходимого числа малочисленных образцов; поскольку основное требование — малочисленные образцы должны встречаться через одинаковые промежутки образцов другого вида и максимально (насколько это возможно) быть рассеяны среди всех позиций, то в зависимости от соотношений \(n\) и \(m\) некоторые позиции могут остаться нетронутыми (для их замещения может не хватить образцов другого (малочисленного) вида) (строка 17)
  6. Далее (строка 20), начинается цикл, который и формирует план перестановок; фактически он перемещает по одному образцу из образцов многочисленного вида, но только те, которые не отмечены  в массиве leave.

Результаты работы кода для некоторых пар значений \(n, m\) даны ниже.

n = 7, m = 5
===================== Input array===================
o|o|o|o|o|o|o|x|x|x|x|x
====================================================
The number of replacements (min): 2
o|o|o|x|o|o|o|x|x|x|o|x
o|o|o|x|o|x|o|x|o|x|o|x
===================== Replacement plan =============
o|o|o|x|o|x|o|x|o|x|o|x
====================================================
n = 17, m = 7
===================== Input array===================
o|o|o|o|o|o|o|o|o|o|o|o|o|o|o|o|o|x|x|x|x|x|x|x
====================================================
The number of  replacements (min): 4
o|o|o|o|o|x|o|o|o|o|o|o|o|o|o|o|o|x|x|x|x|x|o|x
o|o|o|o|o|x|o|o|x|o|o|o|o|o|o|o|o|x|x|x|x|o|o|x
o|o|o|o|o|x|o|o|x|o|o|x|o|o|o|o|o|x|x|o|x|o|o|x
o|o|o|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x
===================== Replacement plan =============
o|o|o|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x|o|o|x
====================================================

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

blog comments powered by Disqus