组间平衡洗牌

Balanced shuffling between groups

我正尝试在 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次重复,我认为没有完美的解决方案,但沿行的计数应尽可能相等(只有轻微的整数差异)

输出将是 'balanced-shuffled' y

的 24 次重复

我尝试编写一个蛮力解决方案,它迭代地添加一个打乱的 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)

它适用于这 2 个示例(几秒钟内)

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')

一个简单的观察是,你可以选择x的任意排列作为初始赋值,然后解决一系列赋值问题,确保后续的每个赋值都尽可能保持平衡。

这是一个 python 实现,

#!/usr/bin/python

"""
filename: random_assign.py
purpose:  demonstrate a straightforward solution to 
          
"""


import networkx as nx
import random as rand

# Problem specification taken directly from OP in question
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']

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

x = map(str,x)

all_x = sorted(list(set(x)))

ny = len(y)
assert ny == len(x) #else something is terribly wrong

x_count = { v : sum( [ _x == v for _x in x ] ) for v in all_x }

iter_count = 13

x0 = [_x for _x in x]
rand.shuffle(x0)
# start with a random permutation
assignments = [x0,]

# initialize histograms
histograms = { _y : { _x : 0 for _x in all_x }  for _y in y }
# update histograms
last_assigment = assignments[-1]
for _y,_x in zip(y,last_assigment):
    histograms[_y][_x] += 1

# if true print only final solution
print_only_final_solution = True

for iter_num in range(iter_count-1):

    G = nx.DiGraph()
    G.add_node('sink',demand=ny)
    for _x in all_x:
        G.add_node(_x)
        G.add_edge(_x,'sink',capacity=x_count[_x]);

    for _y in y:
        min_count = min([ histograms[_y][_x] for _x in all_x ])
        G.add_node(_y,demand=-1)
        # rand_wgts are minor random pertubations of the weights to yeild
        # random preferences for assignments and to ensure a unique solution
        # based on randomness
        rand_wgts = [ i for i in range(len(all_x)) ]
        rand.shuffle(rand_wgts)
        for i,_x in enumerate(all_x):
            wgt = 1000*(histograms[_y][_x] - min_count) + rand_wgts[i]
            G.add_edge(_y,_x,capacity=1,weight=wgt)

    flow_dict = nx.min_cost_flow(G)

    assignment = [ _x for _y in y for _x in all_x if flow_dict[_y][_x] == 1]
    assignments.append(assignment)

    # update histograms
    for _y,_x in zip(y,assignment):
        histograms[_y][_x] += 1

    if not print_only_final_solution or iter_num == iter_count-2:
        print 'assignments:'
        for a in assignments:
            print a
        print ''
        print 'histogram:'
        print '  |',
        for _y in y:
            print _y,' ',
        print ''
        print '--|',
        for _y in y:
            print '-','-',
        print ''
        for _x in all_x:
            print _x, '|',
            for _y in y:
                print histograms[_y][_x], ' ',
            print ''
        print ''

对于分配编号 13,此实现产生 'perfect' 解决方案:

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

注意,大部分随机性是通过选择初始排列作为分配来注入的。之后,问题主要是确定性的,随机性要少得多。尽管如此,此实现通过使用 rand_wgts 注入了少量随机性,这在每个分配中给出了随机(次要)偏好。