Shuffling with constraints on pairs

shuffle_even_pair_constraint.py

# stackoverflow q
# https://stackoverflow.com/questions/54041705/shuffling-with-constraints-on-pairs?fbclid=IwAR1WT2KRYX2YHcgwb1MPt8mRHMZbcLFonWlIwGvpcSCnb5yh9LxYKqdw_X4

from random import randint
from operator import itemgetter


def pop(tmp_d, last_g=1e6):
    tmp = []
    lens = {}
    for it, t in enumerate(tmp_d):
        tmp += t
        lens[it] = len(t)
    lens_list = sorted(lens.items(), key=itemgetter(1), reverse=True)
    max_idx, max_len = lens_list[0]
    others_lens = sum(lens.values()) - max_len
    if max_len > others_lens:
        rint = randint(0, max_len - 1)
        sh_group, sh = tmp_d[max_idx].pop(rint)
        return sh, sh_group, tmp_d
    tmp_len = len(tmp)
    rint = randint(0, tmp_len-1)
    sh_group, sh = tmp.pop(rint)

    pad = 0
    if sh_group > last_g:
        sh_group -= 1
        pad = 1
    t = tmp_d[sh_group]
    if sh_group == 0:
        t.pop(rint)
        lt = [t]
        for w in tmp_d[1:]:
            lt.append(w)
    else:
        lr = rint - sum([len(x) for x in tmp_d[:sh_group]])
        t.pop(lr)
        lt = tmp_d[:sh_group]
        lt.append(t)
        for w in tmp_d[sh_group + 1:]:
            lt.append(w)

    return sh, sh_group + pad, lt


def shuffle_and_pop(lists):
    stop = sum([len(x) for x in lists])
    list_of_lists = list()
    for i, l in enumerate(lists):
        list_of_lists.append([(i, item) for item in l])

    n = 0
    while n < stop:
        if n % 2 != 0:
            exc = list_of_lists.pop(sh_group)
            sh, new_sh_group, tmp_d = pop(list_of_lists, sh_group)
            list_of_lists.insert(sh_group, exc)
            print(sh, end=' ')
            assert new_sh_group != sh_group, 'even pair error'
        else:
            sh, sh_group, list_of_lists = pop(list_of_lists)
            print(sh, end=' ')

        n += 1
    print()


if __name__ == '__main__':
    alphabet = 'abc' #defghijk'
    N = 2 # 10
    for w in range(10000):
        all_lists = list()
        for l in alphabet:
            all_lists.append([f'{l}{j}' for j in range(N)])
        shuffle_and_pop(all_lists)

an attempt to solve this stackoverflow question:
https://stackoverflow.com/questions/54041705/shuffling-with-constraints-on-pairs?fbclid=IwAR1WT2KRYX2YHcgwb1MPt8mRHMZbcLFonWlIwGvpcSCnb5yh9LxYKqdw_X4

1. arrange your lists into a list of lists
2. save each item in the list as a tuple with the list index in the list of lists
3. loop n*m times
4. on even turns - flatten into one list and just rand pop - yield the item and the item group
5. on odd turns - temporarily remove the last item group and pop as before - in the end add the removed group back

important - how to avoid deadlocks?

a deadlock can occur if all the remaining items are from one group only.
to avoid that, check in each iteration the lengths of all the lists
and check if the longest list is longer than the sum of all the others.
if true - pull for that list

that way you are never left with only one list full