Convert integer to base/iterate through all possibilities

Question

I need to iterate through all possible realisations of a vector of length n, each element being a number from 1 to g. There are g^n of these; g is typically 3, while n will be as large as I can reasonably get R to handle. On each realisation I'll calculate something f(z) (where z is the realisation) and add it to a running total (normalising constant of a distribution, if you want to know).

One example with n=10 would be c(1, 2, 3, 1, 2, 3, 1, 1, 2, 2).

I could do this with say some sort of expand.grid cleverness and loop through each row, but is it possible to go through each realisation without holding them all simultaneously in memory?

With the expand.grid (or similar) method where I would generate say a (g^n) * n matrix of z possibilities, I would have to store them all in memory at once.

One option to avoid this is to iterate through all integers from 0 to g^n - 1; convert this to a number in base g (it will have n characters from 0 to g-1); and then add one to get a realisation of z. However, I couldn't find a convenient (fast?) function to convert from an integer to a given base unless that base happened to be 2, 6, or 8.

So, does anyone know how I may convert an integer to a z, or alternatively how I may conveniently construct a loop over all possible z without having to store them all simultaneously at once?

You might find something helpful [here](http://stackoverflow.com/questions/36143323/pythons-xrange-alternative-for-r-or-how-to-loop-over-large-dataset-lazilly) — alexis_laz, Mar 18 '17 at 15:06
A more verbose/documented form of my answer (motivated/improved by @alexis_laz, in fact) is in a [gist](https://gist.github.com/r2evans/e5531cbab8cf421d14ed). — r2evans, Mar 18 '17 at 15:19
The `trotter` package uses pseudo-vectors for combinations: https://cran.r-project.org/web/packages/trotter/index.html — Shape, Mar 18 '17 at 16:23
Thanks guys, will check it out (the gist, alexis_laz' answer, and trotter). I do not see how `transpose()` can answer this question? ("it turns a pair of lists into a list of pairs" - I don't have or need pairs, and if this were extended to say `g-` or `n-`tuples I'd still have to store them all at once in order to iterate, which I'm trying to avoid.) — mathematical.coffee, Mar 20 '17 at 01:25

score 1 · Accepted Answer · answered Mar 18 '17 at 15:37

Here is a way of looping through all possibilities - not sure how fast it would be, but it certainly avoids setting up a large array

n <- 4
g <- 3
a <- rep(1,n) #initialise to a vector of 1s
while(max(a) < g + 1){
  cat(a,"\n") #insert your own function here
  a[1] <- a[1] + 1 #increment first element
  for(i in 2:n){ #this loop 'carries forward'
    if(a[i-1] > g){
      a[i-1] <- 1
      a[i] <- a[i] + 1
    }
  }
}

Convert integer to base/iterate through all possibilities

1 Answers1