Как найти все возможные k целых чисел, сумма которых равна некоторому числу в R

предположим, у меня есть целое числоn а такжеkМне нужно найти все возможные комбинацииk целые числа, которые в суммеn, Мне было интересно, как я могу реализовать это эффективно.

сейчас то, что я делаю, очень медленно, я создалkth декартово произведение последовательности от 1 до n. А затем переберите все возможные комбинации, чтобы проверить, удовлетворяет ли она сумме. Ниже приведен мой код.

сначала получить k декартово произведение

cart = function(v,k){
  x = v
  f = v
  for(i in 1:(k-1)){
    f = merge(f,x,all=T)
    f = as.matrix(f)
    colnames(f) = NULL
  }
  return(f)
}

v - последовательность от 1 до n, а k - целое число.

затем зациклиться

combine = cart(v=seq(1,n),k=k)
sum = 0
for(i in 1:dim(combine)[1]){
  if(sum(combine[i,])==n){
    sum = sum + sum(combine[i,])
  }
}

это очень медленно, и мне было интересно, есть ли более быстрый способ реализовать это?

Ответы на вопрос(2)

Вот базовый метод R с использованиемcombn, Допустим, у вас есть целые числа от 1 до 12, и вы хотите найти все наборы из 5 чисел, которые составляют до 20.

myGroups <- combn(1:12, 5)
mysums <- combn(1:12, 5, FUN=sum, simplify=TRUE)

myAnswers <- myGroups[, mysums == 20]

Это возвращает матрицу, где столбцы являются наборами чисел:

myAnswers
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    1    1    1    1    1    2
[2,]    2    2    2    2    2    3    3
[3,]    3    3    3    4    4    4    4
[4,]    4    5    6    5    6    5    5
[5,]   10    9    8    8    7    7    6

Это будет легко заключить в функцию. В приведенной ниже функции x является входным вектором, который я установил как 1:12 в примере выше, а k и n определены в вопросе OP.

myfunction <- function(x, k, n) {
  myGroups <- combn(x, k)
  mysums <- combn(x, k, FUN=sum, simplify=TRUE)

  myGroups[, mysums == n]
}

Заметка
Этот метод предполагает, что каждая запись в x будет использоваться один раз в расчете, поэтому для целых чисел 0: 9, которые складываются до 9, используя 4 из них,myfunction возвращает:

myfunction(0:9, 4, 9)
     [,1] [,2] [,3]
[1,]    0    0    0
[2,]    1    1    2
[3,]    2    3    3
[4,]    6    5    4

Заметка
Если целью является разрешение на повторное использование этих целых чисел, мы просто должны скорректировать то, что мы кормимmyfunction, Обратите внимание, что это приведет к дублированию вывода наборов, так как порядок имеет значение дляcombn.

Если будут задействованы повторяющиеся целые числа, использованиеcombn должен быть изменен, чтобы вернуть список, чтобы мы могли использоватьunique удалить дубликаты наборов:

myfunctionDupes <- function(x, k, n) {
  # return list instead of matrix, with elements sorted
  myGroups <- lapply(combn(x, k, simplify=FALSE), sort)
  # find duplicates
  dupes <- duplicated(myGroups)
  # subset summations to those where myGroups is not a duplicate
  mysums <- combn(x, k, FUN=sum, simplify=TRUE)[!dupes]
  # subset myGroups to the unique values then those with sums == n
  myGroups <- (myGroups[!dupes])[mysums == n]
  # return a matrix
  do.call(cbind, myGroups)
}

Это займет немного времени для запуска на примере @ josh-obrien, но даст тот же результат:

myfunctionDupes(rep(0:9, 4), 4, 9)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18]
[1,]    0    0    0    0    0    0    0    0    0     0     0     0     1     1     1     1     1     2
[2,]    1    1    1    1    0    2    2    0    0     3     0     0     2     2     1     1     1     2
[3,]    2    3    4    1    1    3    2    2    3     3     4     0     3     2     2     3     1     2
[4,]    6    5    4    7    8    4    5    7    6     3     5     9     3     4     5     4     6     3
 Carl Witthoft28 июн. 2016 г., 19:49
Зачем ограничиватьx к чему-то меньшему, чем1:(n-k+1) ?
 lmo28 июн. 2016 г., 19:53
@CarlWitthoft Извините. Какая часть ограничивает х? Я думаю, что технически функция будет принимать любой вектор (хотя будет работать только с целыми числами).
 lmo28 июн. 2016 г., 19:59
@weikangduan Попробуйте скопировать и вставить мой ответ. Я только что попробовал обе версии в новой сессии R, и они работали.
 Carl Witthoft28 июн. 2016 г., 20:10
Я не могу заставить ваш код работать с 9,4, как в примере с Джошем. Что-то идет не так с меньшими числами. Ой: ваше решение не допускает повторных значений, а его допускает. Я думаю, что ваш не то, что хочет ОП
 Carl Witthoft28 июн. 2016 г., 20:05
Я просто подумал, что мы бы хотели все возможное :-). Кстати, вам не нужноwhich . R будет работать на логических векторах.
 weikangduan28 июн. 2016 г., 21:02
@lmo, я думаю, что я не прояснил свой вопрос, я хочу сгенерировать, например, мне нужно найти k целых чисел, где все они меньше n, а их сумма должна быть равна n. Например, если n = 4 и k = 3, то результат, который я хочу получить, равен 1, 1, 2; 2, 1, 1; 1, 2, 1;
 nik29 июн. 2016 г., 15:11
@lmo понравился твой ответ
 weikangduan28 июн. 2016 г., 19:51
Я получил сообщение об ошибке в combn (x, k, FUN = sum, simpify = TRUE): «FUN» должно быть функцией или NULL, мне было интересно, где что-то пошло не так, спасибо
 lmo28 июн. 2016 г., 21:05
Смотрите мое последнее обновление, которое содержит это как возможность. Единственное, что вам придется кормитьfunctionDupes вектор х, который учитывал бы все возможные комбинации. Посмотрите, например, как я построил вектор в этом примере.
Решение Вопроса

Отредактировано на основе уточнения вопроса в комментариях:

Похоже, вы хотите все композиции, а не все разделы целого числаn, (Две последовательности, отличающиеся только порядком их членов, считаются одинаковымираздел, но разныекомпозиции.)

Чтобы получить композиции, используйтеcompositions() функция отперегородки пакет:

library(partitions)
compositions(4, 3, include.zero=FALSE)
#           
# [1,] 2 1 1
# [2,] 1 2 1
# [3,] 1 1 2

Оригинальный ответ, оставленный на месте, пока автор пакета не сможет его увидеть:

Если я правильно понимаю ваш вопрос, вы можете использоватьrestrictedparts() отперегородки пакет.

Например:

library(partitions)

restrictedparts(9,4)
#                                         
# [1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3
# [2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2
# [3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2
# [4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2

## Or, for partitions employing only non-zero integers
restrictedparts(9,4,include.zero=FALSE)
#                 
# [1,] 6 5 4 4 3 3
# [2,] 1 2 3 2 3 2
# [3,] 1 1 1 2 2 2
# [4,] 1 1 1 1 1 2

Из-за незначительной ошибки во второй-последней строкеrestrictedpartsможет выдать ошибку, если данное ограничение допускает только один раздел. Я отправил предлагаемое исправление автору пакета, но пока вы можете обойти это, установив аргумент функцииdecreasing=FALSE:

## Throws an error
restrictedparts(4,3,include.zero=FALSE)
# Error in class(x) <- "matrix" : 
# invalid to set the class to matrix unless the dimension attribute is of # length 2 (was 0)

## Works just fine
restrictedparts(4,3,include.zero=FALSE,decreasing=FALSE)
#       
# [1,] 1
# [2,] 1
# [3,] 2
 weikangduan28 июн. 2016 г., 23:31
где принять? извините, я новичок здесь
 weikangduan28 июн. 2016 г., 22:54
спасибо за обновление, джош!
 weikangduan28 июн. 2016 г., 22:28
Привет @ Джош, спасибо. Но результат, который я ищу, это 1 1 2, 1 2 1 и 2 2 1. Есть ли способ решить эту проблему? Благодарю.
 Josh O'Brien28 июн. 2016 г., 22:23
@weikangduan Хороший улов. Это из-за ошибки вrestrictedparts(), Смотрите мое редактирование для легкого обхода.
 weikangduan28 июн. 2016 г., 20:32
спасибо, Джош, но я получил ошибку, когда реализовал ограниченные части (4,3, include.zero = F), спасибо
 weikangduan28 июн. 2016 г., 23:34
Большое спасибо за помощь, Джош!
 Josh O'Brien28 июн. 2016 г., 22:53
@weikangduan Это так называемые «композиции», и вы можете получить их, выполнивpartitions::compositions(4, 3, include.zero=FALSE),

Ваш ответ на вопрос