>Dear users
>
>Is there a general algorithm for finding all sets of say k +ve integers that
>sum to S. For
>example, say I need all sets of 3 positve integers that sum to 6 : (1,2,3),
>(1,1,4),(2,2,2).
>
>Thanks
>
>rhoderick
I would do it inductively:
start with the answer for 1,
create answer for k+1 from answers for 1, 2, ... k.
You could also do it recursively, but if you're not careful in programming
it could get extremely slow, with a lot of duplicated effort.
Here is an inductive solution to a similar problem, in case it helps.
> combinations
function(n, k)
{
# Compute all n choose k combinations of size k from 1:n
# Return matrix with k rows and choose(n,k) columns.
if(!is.numeric(n) || length(n) != 1 || n %% 1) stop("'n' must be an integer")
if(!is.numeric(k) || length(k) != 1 || k %% 1)
stop("'k' must be an integer")
if(k > n || k < 0)
return(matrix(numeric(0), 0, 0))
if(k == 0)
return(matrix(numeric(0), 0, 1))
rowMatrix <- function(n) structure(1:n, dim = c(1, n))
colMatrix <- function(n) structure(1:n, dim = c(n, 1))
if(k == n)
return(colMatrix(n))
if(k == 1)
return(rowMatrix(n))
L <- vector("list", k)
# L[[j]] will contain combinations(N, j) for N = 2:n
L[[1]] <- rowMatrix(2)
L[[2]] <- colMatrix(2)
Diff <- n - k
for(N in seq(3, n, by = 1)) {
# loop over j in reverse order, to avoid overwriting
for(j in seq(min(k, N - 1), max(2, N - Diff), by = -1))
L[[j]] <- cbind(L[[j]], rbind(L[[j - 1]], N, deparse.level = 0))
if(N <= Diff + 1)
L[[1]] <- rowMatrix(N)
else L[[N - (Diff + 1)]] <- numeric(0)
if(N <= k)
L[[N]] <- colMatrix(N)
}
L[[k]]
}
Tim Hesterberg
========================================================
| Tim Hesterberg Research Scientist |
| timh@insightful.com Insightful Corp. |
| (206)802-2319 1700 Westlake Ave. N, Suite 500 |
| (206)283-8691 (fax) Seattle, WA 98109-3012, U.S.A. |
| www.insightful.com/Hesterberg |
========================================================
Download the S+Resample library from www.insightful.com/downloads/libraries
Two Research Scientist positions:
data mining
frailty/mixed effects
http://www.insightful.com/company/jobs.asp
Speak out about biased science in Washington D.C.
http://home.comcast.net/~timhesterberg/ScientificIntegrity.html
|