Разделяйте список на случайные куски / комбинации с ограничениями групповой маскировки в Python - PullRequest
1 голос
/ 11 октября 2019

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

В настоящее время я храню матрицу маскирования и строю свои фрагменты итеративно. Пример игрушки ниже. Реальный пример будет иметь около 1000 различных предметов. У кого-нибудь есть идеи получше? Я немного обеспокоен тем, что он слишком часто заглядывает в угол и получает короткие списки элементов.

Результаты запуска 1:

[[2, 7, 3, 0], [5, 6, 4, 1]]
[[6, 4, 5, 3], [2, 1, 7]]
[[4, 6, 3, 1], [2, 0, 7]]

Результаты запуска 2:

[[3, 0, 4, 2], [5, 1, 6]]
[[5, 0, 2, 6], [3, 4, 1, 7]]
[[7, 1, 2, 4], [3, 0, 6, 5]]

игрушечный код:

import numpy as np

REPEAT = 3
NUM_CHUNKS = 2
CHUNK_SIZE = 4


list_idx = np.arange(8)
mtx_mask = np.ones((len(list_idx), len(list_idx)))

#0 and 1 cannot be in same group
mtx_mask[0][1] = 0
mtx_mask[1][0] = 0

#5 and 7 cannot be in same group
mtx_mask[5][7] = 0
mtx_mask[7][5] = 0

for cur_repeat_idx in range(REPEAT):
    #reset probabilities
    cur_overall_prob_mask = np.ones(len(list_idx))

    cur_repeat = []
    for cur_chunk_idx in range(NUM_CHUNKS):   
        cur_chunk = []
        cur_chunk_prob_mask = np.copy(cur_overall_prob_mask)
        while len(cur_chunk) < CHUNK_SIZE:
            #merge overall prob mask and current chunk prob mask
            cur_prob_mask = cur_overall_prob_mask * cur_chunk_prob_mask

            #catch edge case where cannot add any new members to chunk 
            if np.sum(cur_prob_mask) <= 0:
                break

            #select random 
            norm_probs = cur_prob_mask / np.sum(cur_prob_mask)
            choice = np.random.choice(list_idx, p=norm_probs)
            cur_chunk.append(choice)

            #update prob mask to exclude any non-allowed pairs
            cur_overall_prob_mask[choice] = 0.0
            cur_chunk_prob_mask = cur_chunk_prob_mask * mtx_mask[choice] #element-wise updating
        cur_repeat.append(cur_chunk)
    print(cur_repeat)
...