Генерация перестановок с ограничением суммы - PullRequest
Новая
       40

Генерация перестановок с ограничением суммы

0 голосов
/ 18 мая 2018

У меня есть n наборы переменной длины, и я хотел бы получить все перестановки элементов из каждого набора, где сумма находится в определенном диапазоне.Например, в R мы можем сделать: 

set1 <- c(10, 15, 20)
set2 <- c(8, 9)
set3 <- c(1, 2, 3, 4)

permutations <- expand.grid(set1, set2, set3)
permutations$sum <- rowSums(permutations)
final <- permutations[permutations$sum >= 25 & permutations$sum <= 29, ]

# final:
#    Var1 Var2 Var3 sum
# 3    20    8    1  29
# 5    15    9    1  25
# 8    15    8    2  25
# 11   15    9    2  26
# 14   15    8    3  26
# 17   15    9    3  27
# 20   15    8    4  27
# 23   15    9    4  28

Это хорошо для небольшого числа наборов, однако быстро (факториально) растет с большим или большим числом наборов.

Можно ли сгенерировать перестановки, которые соответствуют ограничению, без необходимости расчета всех возможностей?

В этом примере нет окончательных комбинаций, содержащих 10 из set1 в качестве результирующегосумма будет слишком мала независимо от того, какие другие числа выбраны.Это может быть полезно для уменьшения масштабов проблемы.Например, если я знаю, что min(set1) + max(set2) + max(set3) < 25 == TRUE, то я могу убедиться, что не включил min(set1) в какие-либо перестановки.

Как я могу обобщить это и использовать ограничения для предотвращения создания недопустимых перестановок?

1 Ответ

0 голосов
/ 18 мая 2018

Я думаю, что вы просите, это довольно специфично для обуви и вряд ли будет "легко осуществимо" (эффективно).Другой способ взглянуть на это - создать условия во время эксперимента (если предположить, что это план испытаний).

Я написал lazyExpandGrid.R, который похож на концепциюдля ленивого expand.grid, что означает, что он не оценивает все возможные комбинации заранее.Код может быть вставлен позже в этот ответ, если это необходимо, но Github-Gist довольно твердый (и не короткий).

Используя его, вы должны быть в состоянии сделать: 

set1 <- c(10, 15, 20)
set2 <- c(8, 9)
set3 <- c(1, 2, 3, 4)

iter <- lazyExpandGrid(set1, set2, set3)

while (is.data.frame(item <- iter$nextItem())) {
  p <- sum(item)
  if (p < 25 || 29 < p) next
  print(item) # but really, do something more interesting here
}
#   Var1 Var2 Var3
# 3   20    8    1
#   Var1 Var2 Var3
# 5   15    9    1
#   Var1 Var2 Var3
# 8   15    8    2
#    Var1 Var2 Var3
# 11   15    9    2
#    Var1 Var2 Var3
# 14   15    8    3
#    Var1 Var2 Var3
# 17   15    9    3
#    Var1 Var2 Var3
# 20   15    8    4
#    Var1 Var2 Var3
# 23   15    9    4

Caveat emptor: функция в основном пригодна для использования, но, безусловно, есть способы ее улучшения.Например, использование is.data.frame(item <- iter$nextItem()) фактически является тестом isTruthy (название из shiny);в настоящее время он возвращает 1 строку data.frame до тех пор, пока ничего не останется, затем возвращает FALSE.Сейчас, когда я смотрю на это, это, безусловно, можно улучшить, у меня просто не было необходимости.Не стесняйтесь комментировать на странице GitHub Gist, если у вас есть мысли, ошибки и т. Д.

...