Как правило, эти типы проблем могут быть обработаны пакетом partitions, однако я не смог найти решение с помощью этого пакета. Я бы пока не исключал этот пакет, так как за последние несколько лет я постоянно обнаруживал действительно приятные сюрпризы. Я отвлекся.
Во-первых, минимальное количество натуральных чисел, равное 274, равно 274 (например, sum(rep(1, 274))). Таким образом, любое решение с более чем 274 элементами, скажем, n , будет идентичным, за исключением дополнительных n - 274 нулей на комбинацию.
В качестве примера, демонстрирующего это, скажем, мы ищем каждую комбинацию из 10 элементов, которые составляют 8, где каждый элемент представляет собой целое число от 0 до 2. Единственные решения:
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 0 0 0 0 0 0 2 2 2 2
[2,] 0 0 0 0 0 1 1 2 2 2
[3,] 0 0 0 0 1 1 1 1 2 2
[4,] 0 0 0 1 1 1 1 1 1 2
[5,] 0 0 1 1 1 1 1 1 1 1
Как видите, в последней строке содержится максимальное количество положительных элементов (то есть 8 элементов).
Это важное наблюдение, потому что мы можем значительно сократить количество проверяемых комбинаций, ограничив количество элементов до желаемой суммы.
Число комбинаций с повторением из n элементов выбора k задается биномиальным коэффициентом, где верхнее число равно n + k - 1 , а нижний номер k :
Таким образом, для нашего примера мы можем сократить количество возможных проверок более чем на 20 миллионов:
choose(280 + 5 - 1, 280)
[1] 265368251
choose(274 + 5 - 1, 274)
[1] 243531475
265368251 - 243531475
[1] 21836776
Хотя мы сократили пространство возможностей, нам все еще предстоит трудная задача. Генерация всех комбинаций и проверка их суммы вряд ли приведут к каким-либо решениям в разумные сроки.
Более разумным решением является исключение множества комбинаций без проверки их суммы. Создавая комбинации в лексикографическом порядке, когда конкретная комбинация превышает ограничение, мы можем пропустить многие комбинации, зная, что они тоже превысят ограничение. Это именно то, что comboGeneral из RcppAlgos (я автор) делает.
library(RcppAlgos)
comb274 <- comboGeneral(0:4, m = 274, TRUE,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = 274)
Error: vector memory exhausted (limit reached?)
Как вы можете видеть, в исходном виде это не сработает, так как слишком много комбинаций для тестирования (по крайней мере, на моем компьютере ... вы можете изменить пределы памяти в R на macOS R в MacOS Ошибка: векторная память исчерпана (предел достигнут?) ).
Это не проблема. Все, что нам нужно сделать, это ограничить число ожидаемых результатов с помощью параметра upper. Я произвольно установлю его на 1 миллион. Если мы получим 1 миллион результатов, мы увеличиваем этот предел до тех пор, пока число результатов не станет меньше нашего.
system.time(comb274 <- comboGeneral(0:4, m = 274, TRUE,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = 274,
upper = 1e6))
user system elapsed
3.624 0.079 3.705
dim(comb274)
[1] 150811 274
И вот оно у вас! Подтверждая, что каждая строка равна 274, мы имеем:
all(rowSums(comb274) == 274)
[1] TRUE
Если вам действительно нужно 280 элементов, вы можете запустить приведенный выше код, задав для параметра m значение 280, за счет эффективности или просто cbind матрицу нулей со 150811 строками и 6 столбцами для comb274 .