Сбалансированное переключение между группами

Question

Я пытаюсь написать алгоритм в python для следующей проблемы:

Учитывая эти 2 массива одинаковой длины, объекты в y уникальны

x = (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7)
y = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M')

Случайным образом назначьте каждый объект в y позиции в x Повторите 24 раз

например,

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7]
['A', 'M', 'E', 'D', 'G', 'L', 'K', 'J', 'C', 'F', 'H', 'I', 'B']
['B', 'C', 'G', 'E', 'L', 'J', 'H', 'F', 'A', 'M', 'D', 'I', 'K']
['F', 'E', 'H', 'I', 'A', 'K', 'L', 'D', 'B', 'G', 'M', 'C', 'J']
['M', 'I', 'E', 'F', 'H', 'C', 'D', 'B', 'L', 'A', 'K', 'J', 'G']
.
.
.

Однако выполните случайное присвоение, чтобы в конце каждый объект в y был назначен каждому уникальному объекту в x в максимально равное возможное число.

например, для 13 повторов вместо 24 подсчет присваиваний будет соответствовать такому:

    A   B   C   D   E   F   G   H   I   J   K   L   M
1   2   2   2   2   2   2   2   2   2   2   2   2   2
2   2   2   2   2   2   2   2   2   2   2   2   2   2
3   2   2   2   2   2   2   2   2   2   2   2   2   2
4   2   2   2   2   2   2   2   2   2   2   2   2   2
5   2   2   2   2   2   2   2   2   2   2   2   2   2
6   2   2   2   2   2   2   2   2   2   2   2   2   2
7   1   1   1   1   1   1   1   1   1   1   1   1   1

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

Тогда на выходе будут 24 повтора «сбалансированного- shuffled 'y

Я попытался написать решение грубой силы, которое итеративно добавляет перемешанный y и перезапускается каждый раз, когда он слишком сильно выходит из баланса. Он находит решение для более простого варианта, но здесь он терпит неудачу. Может быть, у вас есть простое решение этой проблемы?

ОБНОВЛЕНИЕ Я написал алгоритм грубой силы, который находит оптимальное решение, используя минимально возможное количество повторов (len (y)). Однако он не масштабируется до y = len (13), что мне нужно.

def find_optimal_set(x, y):
    repeats = len(y)
    groups = set(x)
    while True:
        asig = {k:{k:0 for k in y} for k in groups}
        s = [random.sample(y, repeats) for i in range(repeats)]
        for r in s:
            for i, c in enumerate(r):
                asig[x[i]][c] +=1
        if all([len(set(v.values())) == 1 for v in asig.values()]):
            return(asig, s)

Он работает с этими двумя примерами (в течение секунд)

x = (1, 1, 1, 2, 3, 3)
y = ('A', 'B', 'C', 'D', 'E', 'F')

x = (1, 1, 2, 2, 3)
y = ('A', 'B', 'C', 'D', 'E')

Answer 1

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

Вот реализация python, которая сбрасывает это,

Для номера назначения 13 эта реализация дает «идеальное» решение:

assignments:
['6', '2', '3', '4', '2', '7', '1', '5', '6', '4', '5', '3', '1']
['5', '3', '7', '6', '5', '2', '6', '3', '1', '1', '2', '4', '4']
['1', '4', '2', '5', '4', '6', '3', '1', '7', '2', '6', '5', '3']
['3', '5', '4', '1', '6', '5', '2', '2', '4', '3', '1', '7', '6']
['7', '6', '1', '3', '3', '1', '4', '6', '5', '5', '4', '2', '2']
['4', '7', '6', '2', '1', '3', '5', '4', '2', '6', '3', '1', '5']
['2', '1', '5', '4', '2', '4', '5', '3', '3', '7', '6', '6', '1']
['5', '3', '6', '6', '4', '4', '7', '5', '3', '1', '2', '1', '2']
['3', '2', '4', '2', '5', '6', '4', '1', '1', '5', '7', '3', '6']
['4', '6', '5', '7', '1', '3', '1', '2', '4', '2', '3', '6', '5']
['2', '4', '1', '5', '3', '1', '2', '6', '6', '3', '4', '5', '7']
['1', '1', '3', '3', '6', '5', '6', '7', '2', '4', '5', '2', '4']
['6', '5', '2', '1', '7', '2', '3', '4', '5', '6', '1', '4', '3']

histogram:
  | A   B   C   D   E   F   G   H   I   J   K   L   M
--| - - - - - - - - - - - - - - - - - - - - - - - - - -
1 | 2   2   2   2   2   2   2   2   2   2   2   2   2
2 | 2   2   2   2   2   2   2   2   2   2   2   2   2
3 | 2   2   2   2   2   2   2   2   2   2   2   2   2
4 | 2   2   2   2   2   2   2   2   2   2   2   2   2
5 | 2   2   2   2   2   2   2   2   2   2   2   2   2
6 | 2   2   2   2   2   2   2   2   2   2   2   2   2
7 | 1   1   1   1   1   1   1   1   1   1   1   1   1

Для 24, это дает:

assignments:
['6', '1', '3', '4', '1', '5', '4', '5', '3', '2', '2', '7', '6']
['5', '2', '4', '6', '7', '3', '1', '3', '1', '4', '6', '2', '5']
['7', '5', '2', '3', '3', '4', '5', '6', '6', '1', '1', '4', '2']
['4', '3', '6', '5', '2', '6', '2', '4', '7', '3', '5', '1', '1']
['1', '4', '5', '1', '6', '2', '6', '2', '5', '7', '3', '3', '4']
['2', '6', '7', '2', '5', '1', '3', '1', '4', '6', '4', '5', '3']
['3', '7', '1', '2', '4', '1', '6', '3', '2', '5', '4', '6', '5']
['5', '6', '1', '1', '2', '6', '5', '7', '4', '3', '2', '4', '3']
['4', '1', '5', '7', '6', '3', '2', '4', '6', '1', '3', '5', '2']
['1', '3', '6', '4', '3', '2', '7', '2', '5', '5', '6', '1', '4']
['6', '4', '3', '6', '5', '5', '4', '1', '3', '2', '1', '2', '7']
['2', '5', '2', '3', '4', '4', '1', '5', '1', '6', '7', '3', '6']
['3', '2', '4', '5', '1', '7', '3', '6', '2', '4', '5', '6', '1']
['7', '5', '3', '6', '3', '1', '4', '2', '4', '5', '6', '2', '1']
['5', '1', '4', '2', '4', '2', '7', '6', '1', '3', '3', '5', '6']
['3', '7', '1', '4', '6', '5', '6', '1', '2', '2', '5', '3', '4']
['2', '2', '6', '1', '7', '4', '5', '3', '5', '6', '4', '1', '3']
['4', '3', '2', '5', '2', '6', '3', '4', '7', '1', '1', '6', '5']
['1', '6', '7', '3', '5', '3', '1', '5', '6', '4', '2', '4', '2']
['6', '4', '5', '4', '1', '1', '2', '5', '3', '7', '2', '6', '3']
['6', '5', '1', '3', '2', '6', '2', '3', '4', '4', '5', '1', '7']
['5', '1', '2', '6', '4', '3', '3', '6', '2', '5', '4', '7', '1']
['2', '3', '5', '1', '6', '2', '1', '4', '5', '3', '7', '4', '6']
['3', '6', '4', '2', '1', '5', '4', '7', '3', '6', '1', '5', '2']

histogram:
  | A   B   C   D   E   F   G   H   I   J   K   L   M
--| - - - - - - - - - - - - - - - - - - - - - - - - - -
1 | 3   4   4   4   4   4   4   3   3   3   4   4   4
2 | 4   3   4   4   4   4   4   3   4   3   4   3   4
3 | 4   4   3   4   3   4   4   4   4   4   3   3   4
4 | 3   3   4   4   4   3   4   4   4   4   4   4   3
5 | 4   4   4   3   3   4   3   4   4   4   4   4   3
6 | 4   4   3   4   4   4   3   4   3   4   3   4   4
7 | 2   2   2   1   2   1   2   2   2   2   2   2   2

А для 26 это дает другое идеальное решение:

assignments:
['5', '1', '1', '6', '7', '6', '4', '5', '2', '4', '2', '3', '3']
['1', '2', '4', '4', '5', '7', '5', '2', '1', '3', '3', '6', '6']
['3', '5', '6', '3', '1', '2', '2', '4', '5', '7', '6', '4', '1']
['2', '3', '5', '2', '4', '1', '1', '6', '3', '6', '4', '5', '7']
['6', '4', '2', '1', '3', '4', '3', '1', '6', '5', '7', '2', '5']
['4', '6', '7', '5', '2', '3', '6', '3', '4', '1', '5', '1', '2']
['6', '2', '3', '5', '6', '5', '3', '7', '1', '2', '1', '4', '4']
['5', '5', '6', '2', '1', '2', '7', '4', '3', '1', '6', '3', '4']
['1', '4', '1', '7', '3', '6', '2', '3', '6', '4', '5', '2', '5']
['4', '1', '5', '3', '6', '3', '4', '1', '7', '6', '2', '5', '2']
['2', '7', '2', '1', '4', '1', '5', '6', '4', '5', '3', '6', '3']
['7', '3', '3', '6', '2', '4', '1', '5', '5', '2', '4', '1', '6']
['3', '6', '4', '4', '5', '5', '6', '2', '2', '3', '1', '7', '1']
['4', '3', '2', '5', '6', '5', '1', '4', '3', '2', '6', '7', '1']
['6', '5', '4', '2', '5', '7', '3', '1', '2', '1', '3', '4', '6']
['1', '4', '6', '6', '2', '2', '7', '3', '5', '3', '4', '1', '5']
['5', '2', '1', '4', '1', '6', '5', '7', '4', '6', '2', '3', '3']
['2', '1', '5', '3', '4', '3', '2', '6', '1', '4', '5', '6', '7']
['3', '6', '7', '1', '3', '4', '4', '5', '6', '5', '1', '2', '2']
['1', '2', '3', '3', '4', '1', '6', '2', '5', '7', '6', '5', '4']
['6', '3', '1', '5', '6', '2', '1', '4', '7', '3', '5', '4', '2']
['3', '4', '4', '1', '7', '6', '5', '3', '2', '6', '2', '5', '1']
['7', '6', '3', '6', '5', '5', '4', '2', '1', '4', '1', '2', '3']
['2', '7', '6', '2', '1', '3', '6', '5', '3', '5', '4', '1', '4']
['5', '1', '5', '4', '3', '4', '2', '1', '6', '2', '7', '3', '6']
['4', '5', '2', '7', '2', '1', '3', '6', '4', '1', '3', '6', '5']

histogram:
  | A   B   C   D   E   F   G   H   I   J   K   L   M
--| - - - - - - - - - - - - - - - - - - - - - - - - - -
1 | 4   4   4   4   4   4   4   4   4   4   4   4   4
2 | 4   4   4   4   4   4   4   4   4   4   4   4   4
3 | 4   4   4   4   4   4   4   4   4   4   4   4   4
4 | 4   4   4   4   4   4   4   4   4   4   4   4   4
5 | 4   4   4   4   4   4   4   4   4   4   4   4   4
6 | 4   4   4   4   4   4   4   4   4   4   4   4   4
7 | 2   2   2   2   2   2   2   2   2   2   2   2   2

Обратите внимание, что большая часть случайности вводится выбором начальной перестановки, выбранной в качестве присваивания. Впоследствии проблема в основном заключается в детерминированности c с гораздо меньшей случайностью. Тем не менее, эта реализация вносит незначительные количества случайности за счет использования rand_wgts, который дает случайное (незначительное) предпочтение в каждом назначении.