How to produce combinations iteratively in R?

Question

So I am currently using the following code to generate my combinations:

combn(x,y)

But the thing is that function stores all of the possible combinations. I dont want to store them, I just want to produce them through like a loop or something. It would be way more efficient for my program. Is there a way to generate combinations through a for loop rather than storing them all?

I know I asked a similar question here: How do I find all possible subsets of a set iteratively in R?

But in that solution the combinations are still being stored...

Here is some more detail:

Lets say I want to find 4 choose 2. combn(4,2) would essentially store the following: ((1,4),(1,3),(1,2),(2,4),(2,3)(3,4))

What I want is this:

   loop{
       produces one combination at a time 
   }

yea but in that answer the combinations are still being stored — user2560984, Jul 16 '13 at 17:40
I think what OP wants here is a function that doesn't just output all possible combinations, but takes an additional variable, say `i` that gets the ith value of `combn(x,y)`. Although `function(x,y,i)combn(x,y)[i]` would technically work, it would not be efficient. — nograpes, Jul 16 '13 at 18:07
Not sure if this is applicable but often data.table is helpful for improving performance: http://stackoverflow.com/questions/16919998/subtract-every-column-from-each-other-column-in-a-r-data-table — screechOwl, Jul 16 '13 at 18:08
Maybe you find an algorithm at [rosettacode](http://rosettacode.org/wiki/Combinations) — Karsten W., Jul 17 '13 at 00:56
Having a read through the comments, is the OP after a random walk through potential combinations? The only reason (that I can think of) to not store all the combinations is if you're not going to evaluate them. So this leaves the OP wanting to sample a set of combinations. I'd be interested to hear! — MikeRSpencer, Aug 16 '15 at 20:53

score 2 · Answer 1 · answered Jul 22 '13 at 12:28

Here is a suggestion which allows to generate the combination for the current iteration of the loop based on the combination used in the previous iteration of the loop.

## Function definition
gen.next.cbn <- function(cbn, n){
    ## Generates the combination that follows the one provided as input
    cbn.bin      <- rep(0, n)
    cbn.bin[cbn] <- 1
    if (tail(cbn.bin, 1) == 0){
        ind <- tail(which(cbn.bin == 1), 1)
        cbn.bin[c(ind, ind+1)] <- c(0, 1)
    }else{
        ind <- 1 + tail(which(diff(cbn.bin) == -1), 1)
        nb  <- sum(cbn.bin[-c(1:ind)] == 1)
        cbn.bin[c(ind-1, (n-nb+1):n)] <- 0
        cbn.bin[ind:(ind+nb)]         <- 1
    }
    cbn <- which(cbn.bin == 1)
}

## Example parameters
n   <- 6
k   <- 3

## Iteration example
for (i in 1:choose(n, k)){
    if (i == 1){
        cbn <- 1:k
    }else{
        cbn <- gen.next.cbn(cbn, n)
    }
    print(cbn)
}

# [1] 1 2 3
# [1] 1 2 4
# [1] 1 2 5
# [1] 1 2 6
# [1] 1 3 4
# [1] 1 3 5
# [1] 1 3 6
# [1] 1 4 5
# [1] 1 4 6
# [1] 1 5 6
# [1] 2 3 4
# [1] 2 3 5
# [1] 2 3 6
# [1] 2 4 5
# [1] 2 4 6
# [1] 2 5 6
# [1] 3 4 5
# [1] 3 4 6
# [1] 3 5 6
# [1] 4 5 6

@user2560984, did this work for you? – QuantIbex Aug 05 '13 at 12:04 — QuantIbex, Aug 05 '13 at 12:04

canary_in_the_data_mine · Answer 2 · 2013-07-17T16:47:09.223

1

To return each of the possible combinations, one at a time, in a loop, do the following:

#Sample data:
x <- c(1,2,3,4)
y <- 2
all_combinations <- combn(x,y)

#Return each value:
for (i in 1:ncol(all_combinations)) {
  print(all_combinations[,i])
}

But I'm not sure why you want to do this in a for loop, given that it's pretty slow. Is there a desired final output beyond this application?

edited Jul 17 '13 at 16:47

answered Jul 16 '13 at 18:09

canary_in_the_data_mine

2,039
2
22
26

I added more detail to my question. – user2560984 Jul 16 '13 at 19:44
Thanks for the detail. This answer should work for you, then. For instance, `sample(1:4,2)`. – canary_in_the_data_mine Jul 16 '13 at 20:03
I don't think that works because it generates each combination randomly right? – user2560984 Jul 17 '13 at 13:29
Ah, @user2560984. See update. – canary_in_the_data_mine Jul 17 '13 at 16:48
but then you are storing the values which is what I don't want... – user2560984 Jul 18 '13 at 18:24
I'll be honest: at this point I have no idea what you're trying to accomplish. Why are you opposed to storing the values? If you're looking to return each item in the entire set once and only once, then you need to generate the entire list either the first time you do it or every time you do it. – canary_in_the_data_mine Jul 18 '13 at 20:49
the reason I don't want to store it is because i'll be dealing with very large numbers. For example, lets say I want to calculate 1000 choose 3. It wouldn't make sense to store so many combinations when all I need to do is just use one combination at a time, and them move on to the next one. – user2560984 Jul 19 '13 at 17:37

score 1 · Answer 3 · answered Jul 16 '13 at 19:13

1

If the aim is to use each combination as an input for some computations, you might want to use the FUN argument of combn, a la apply. It seems that this won't store the combinations, but will still return at once the result of the function applied to each combination.

Here is an example with a dummy function:

fct <- function(x, y){sum(x*y) + 2*x[1]}
y   <- 1:5
system.time(combn(1:20, 5, fct, y = y))
# user  system elapsed 
# 0.160   0.000   0.161 
system.time(apply(combn(1:20, 5), 2, fct, y = y))
# user  system elapsed 
# 0.224   0.000   0.222

answered Jul 16 '13 at 19:13

QuantIbex

2,234
1
13
17

I added more detail to my question. – user2560984 Jul 16 '13 at 19:44
This would see to be the best solution, assuming that you want to capture each return value. Otherwise, why not take a look at the code for `combn` and adapt that to your needs? – Matthew Lundberg Jul 17 '13 at 17:16

How to produce combinations iteratively in R?

3 Answers3

Linked