Balanced shuffling between groups

Question

I'm trying to write an algorithm in python for the following problem:

Given these 2 arrays of equal length, objects in y are unique

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

Randomly assign each object in y to a position in x
Repeat 24 times

e.g.

[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']
.
.
.

However, perform the random assignment so that in the end, each object in y is assigned to each unique object in x in the most equal number possible.

e.g. for 13 repeats instead of 24, the assignment counts would fit perfectly like this:

    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

Note that the column sums always have to be the number of repeats. For the 24 repeats, there is no perfect solution, I think, but the counts along the rows should be as equal as possible (only slight integer differences)

The output would then be the 24 repeats of 'balanced-shuffled' y

I tried to write a brute force solution that iteratively adds a shuffled y and restarts every time when it got out of balance too much. It finds a solution for a simpler variation, but here it fails. Maybe you have a straight forward solution for that problem?

UPDATE
I wrote a brute force algorithm that finds an optimal solution using the smallest possible number of repeats (len(y)). It does however not scale to y=len(13), which I need.

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)

It works with these 2 examples (within seconds)

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

user_177931 · Answer

A simple observation is that you can choose any permutation of x as the initial assignment, then solve a series of assignment problems that ensure that each subsequent assignment tries to maintain the balance as best as possible.

Here is a python implementation that flushes this out,

#!/usr/bin/python

"""
filename: random_assign.py
purpose:  demonstrate a straightforward solution to 
          https://stackoverflow.com/questions/63250967/balanced-shuffling-between-groups
"""


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

For the assignment number of 13, this implementation yields the 'perfect' solution:

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

For 24, this yields:

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

And for 26 this yeilds another perfect solution:

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

Note, most of the randomness is injected by the choice of the initial permutation selected as an assignment. Afterwards, the problem is mostly deterministic, with a lot less randomness. Nonetheless, this implementation injects minor amounts of randomness through the use of rand_wgts which give a random (minor) preference in each assignment.

Balanced shuffling between groups

1 Answers