CODEWITHSUNDEEP
rrecursion
sg7544
sg7544

Reputation: 13

How to write a recursive function in R to generate dynamic nested for-loops?

I need to generate all possible combinations of 'n' variables such that the variables sum up to 100. The range of variables lie from 0 to 100 and can vary steps of 1. I have created a code for this in R considering n = 10, the resulting data frame contains all the possible combinations. However, I am looking for a possibility to make 'n' dynamic, such that the user has the flexibility to pass n as an argument at initiation. Any help will be highly appreciated.. 

row <- list()
z = 1
for (a in seq(from = 0, to = 100, by = 1)) {
  for (b in seq(from = 0, to = 100, by = 1)) {
    for (c in seq(from = 0, to = 100, by = 1)) {
      for (d in seq(from = 0, to = 100, by = 1)) {
        for (e in seq(from = 0, to = 100, by = 1)) {
          for (f in seq(from = 0, to = 100, by = 1)) {
            for (g in seq(from = 0, to = 100, by = 1)) {
              for (h in seq(from = 0, to = 100, by = 1)) {
                for (i in seq(from = 0, to = 100, by = 1)) {
                  for (j in seq(from = 0, to = 100, by = 1)) {
                    if (a + b + c + d + e + f + g + h + i + j == 100) {
                      row[[z]] <- (c(a,b,c,d,e,f,g,h,i,j))
                      z = z + 1
                    }    
                  }
                }
              }
            }
          }
        }        
      }        
    }
  }
}

finaldata <- as.data.frame(do.call(rbind, row))

Upvotes: 1

Views: 735

Answers (2)

jogo
jogo

Reputation: 12559

parti <- function(n, k) {
  if (n<0) { message("error: n<0"); return(NA) }
  if (k==1) return(matrix(n,1,1))
  M <- cbind(parti(n, k-1), 0)
  if (n>0) for (i in 1:n) M <- rbind(M, cbind(parti(n-i, k-1), i))
  M
}

parti(5, 3)

result:

> parti(5, 3)
        i  
 [1,] 5 0 0
 [2,] 4 1 0
 [3,] 3 2 0
 [4,] 2 3 0
 [5,] 1 4 0
 [6,] 0 5 0
 [7,] 4 0 1
 [8,] 3 1 1
 [9,] 2 2 1
[10,] 1 3 1
[11,] 0 4 1
[12,] 3 0 2
[13,] 2 1 2
[14,] 1 2 2
[15,] 0 3 2
[16,] 2 0 3
[17,] 1 1 3
[18,] 0 2 3
[19,] 1 0 4
[20,] 0 1 4
[21,] 0 0 5

For your situation (n=100, k=10) you will have trouble with memory and time because there are many partitions!

Upvotes: 0

bgoldst
bgoldst

Reputation: 35314

ptn <- function(n,k) if (k<=1L) list(n) else do.call(c,lapply(seq_len(n+1L)-1L,function(x) lapply(ptn(x,k-1L),c,n-x)));

Demos:

ptn(1,1);
## [[1]]
## [1] 1
##

ptn(2,1);
## [[1]]
## [1] 2
##

ptn(1,2);
## [[1]]
## [1] 0 1
##
## [[2]]
## [1] 1 0
##

ptn(2,2);
## [[1]]
## [1] 0 2
##
## [[2]]
## [1] 1 1
##
## [[3]]
## [1] 2 0
##

ptn(3,2);
## [[1]]
## [1] 0 3
##
## [[2]]
## [1] 1 2
##
## [[3]]
## [1] 2 1
##
## [[4]]
## [1] 3 0
##

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

It is impractical to generate the partition set you want, i.e. making 100 from 10. Even making 100 from 5 is pushing it:

system.time({ x <- ptn(100,5); });
##    user  system elapsed
##  32.594   0.141  32.790
length(x);
## [1] 4598126
system.time({ print(unique(sapply(x,sum))); });
## [1] 100
##    user  system elapsed
##   6.938   0.063   7.004
length(unique(x));
## [1] 4598126

Here, I also wrote a function that recursively calculates the size of the partition set, without incurring the CPU or memory cost of actually generating the set. Note: The cache was essential, otherwise the CPU hit would be similar to the full generation algorithm.

ptnSize <- function(n,k,cache=new.env()) if (k<=1L) 1 else { key <- paste0(n,'/',k); if (is.null(cache[[key]])) cache[[key]] <- do.call(sum,lapply(seq_len(n+1L)-1L,function(x) ptnSize(x,k-1L,cache))); cache[[key]]; };

Demos:

ptnSize(1,1);
## [1] 1
ptnSize(2,1);
## [1] 1
ptnSize(1,2);
## [1] 2
ptnSize(2,2);
## [1] 3
ptnSize(3,2);
## [1] 4
ptnSize(3,3);
## [1] 10
ptnSize(100,5);
## [1] 4598126
ptnSize(100,10);
## [1] 4.263422e+12

As we can see, your desired partition set is rather large. I estimate it would require hundreds of terabytes of memory to store.

Upvotes: 1

Related Questions