Присвоение единиц объекта группам без присвоения единицам одного и того же объекта группе

Question

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

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

Входные данные:

Вектор o , содержащий доступные единицы объекта, от каждого объекта до Могут быть доступны единицы p-1 . Пример для o : (0, 1, 5, 8, p-1, ...)

Кроме того, существует вектор g , содержащий доступные пятна в группах , Каждая группа может принимать либо p , либо p + 1 единиц. Пример для g : (p, p + 1, p, p, p + 1, ...)

На входные данные распространяется следующее ограничение:

• Во всех группах достаточно мест для всех доступных объектов. Sum (o) == sum (g)

Ожидаемый результат

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

Пример

Пример 1:

elements <- c(2, 1)
group_sizes <- c(1, 2)

Единственное возможное решение -

(1), (1, 2) 

Объяснение: 1 Единица первого объекта в первой группе, группы содержат одну единицу обоих объектов

Пример 2:

elements <- c(2,1,1)
group_sizes <- c(1, 2, 1)

Возможные решения :

(1), (1, 2), (3)
(1), (1, 3), (2)
(1), (2, 3), (1)
(2), (1, 3), (1)
(3), (1, 2), (1)

Я ищу алгоритм, возвращающий для заданного входа одно из возможных распределений. Все дистрибутивы должны иметь одинаковый шанс на возврат.

** Мой неудачный подход **

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

# Group sizes
group_sizes <- c(8,9,9,9,9,9,9,8,8)
# Available units of objects (already sorted by size)
object_units <- c(8,8,8,8,8,8,8,8,8,6)

# Generate a distributions order
dist_order <- numeric(0)

while(max(object_units) > 0){
  dist_order <- c(dist_order, which(object_units > 0))
  object_units <- object_units - 1 
}


n_groups <- length(group_sizes)

result <- matrix(numeric(0), ncol = n_groups, nrow = min(group_sizes))

set.seed(1)

# distribute batch with
for(i in 1:min(group_sizes)){
  # get the objects of which units are distributed in this batch
  ind <- (i - 1) * n_groups + 1
  current <- v[ind:(ind +  n_groups - 1)]
  # beginning with the batch all groups can be distributed
  avail_groups <- 1: n_groups

  #iterate over groups an select object to assign to group
  for (j in 1:n_groups) {
    # current object can only be assigned to where it has not been assigned yet
    free <- which(colSums(result == current[j], na.rm = TRUE) == 0)
    # current object can only be assigned to where no other object has been assigned to in this batch
    current_avail_groups <- intersect(avail_groups, free)

    # select from remaining groups on to assign the assign the object
    if(length(current_avail_groups) == 1){
      selected_group <- current_avail_groups
    } else {
      selected_group <- sample(current_avail_groups, size = 1)
    }
    # store assignment in result matrix
    result[i, selected_group] <- current[j]
    # remove group from available groups for this iteration
    avail_groups <- avail_groups[selected_group != avail_groups]
  }

}

Это недопустимый алгоритм, так как в некоторый момент для какого-либо объекта все группы могут либо уже содержат единицу объекта, либо уже получили единицу другого объекта в этой итерации.