0

If I have, say, n = seven binary objects, and say, k = three of them equal one, how can I enumerate all 35 permutations of 7 choose 3 in R? For example, 1110000 is one such permutation (and a reasonable starting point to work through the remaining 34). I can write a non-recursive algorithm specifically for 7 choose 3 by nesting three loops by doing something like the following (with hard-coded numbers):

n2Ck <- function() {
    output <- NULL
    out <- as.numeric(c(rep(1,times=3),rep(0, times=4)))
    for (i in 1:5) {
        for (j in (i+1):6) {
            for (k in (j+1):7) {
                out <- out*0
                out[c(i,j,k)] <- 1
                output <- rbind(output,out)
                }
            }
        }
    return(output)
    }

Which produces:

nC2k()
    [,1] [,2] [,3] [,4] [,5] [,6] [,7]
out    1    1    1    0    0    0    0
out    1    1    0    1    0    0    0
out    1    1    0    0    1    0    0
out    1    1    0    0    0    1    0
out    1    1    0    0    0    0    1
out    1    0    1    1    0    0    0
out    1    0    1    0    1    0    0
out    1    0    1    0    0    1    0
out    1    0    1    0    0    0    1
out    1    0    0    1    1    0    0
out    1    0    0    1    0    1    0
out    1    0    0    1    0    0    1
out    1    0    0    0    1    1    0
out    1    0    0    0    1    0    1
out    1    0    0    0    0    1    1
out    0    1    1    1    0    0    0
out    0    1    1    0    1    0    0
out    0    1    1    0    0    1    0
out    0    1    1    0    0    0    1
out    0    1    0    1    1    0    0
out    0    1    0    1    0    1    0
out    0    1    0    1    0    0    1
out    0    1    0    0    1    1    0
out    0    1    0    0    1    0    1
out    0    1    0    0    0    1    1
out    0    0    1    1    1    0    0
out    0    0    1    1    0    1    0
out    0    0    1    1    0    0    1
out    0    0    1    0    1    1    0
out    0    0    1    0    1    0    1
out    0    0    1    0    0    1    1
out    0    0    0    1    1    1    0
out    0    0    0    1    1    0    1
out    0    0    0    1    0    1    1
out    0    0    0    0    1    1    1

But I don't know how to produce a function for arbitrary n and k. (Output format is fairly arbitrary here, BTW.)

I have seen some recursive solutions to this kind of problem in other languages (for example, here, and here), but I am really poor at recursion, and have been unable to understand them enough to translate these algorithms into R. I understand that the recursive solutions want to break down the problem into one of two categories: those where the first element is 1 for (n-1,k-1), and those where the first element is 0 for (n-1,k), but I get lost in how to implement (I wish there was a newb tag for this question... I would be delighted to improve this question if you have feedback for me).

Community
  • 1
  • 1
Alexis
  • 784
  • 8
  • 32
  • 2
    How about `combinat::combn(7, 3)`, taking the returned numbers as the indices of the 1s? – Gregor Thomas Sep 20 '16 at 20:57
  • @Gregor Thank you... I see how that works, and that *will* provide me with a solution for my larger problem which this question is motivated by. :) That said, any chance you can help me understand creating a recursive function to solve the problem? – Alexis Sep 20 '16 at 20:59
  • 1
    The recursive solution does sound fun - I don't have time to answer now but I'll hope to find time later tonight. – Gregor Thomas Sep 20 '16 at 21:03
  • @Gregor You are very kind. Is there a `self-study`-type tag on SO the way there is on CV stack-exchange? – Alexis Sep 20 '16 at 21:04

1 Answers1

1

Here, is sample code for solving your problem in R. The selected vector is used for storing selected object index.

# your code goes here
n <- 9
k <- 5
count <- 0
selected <- vector( 'numeric' , k )

rec <- function(x,y) {
    if (y == 0){
        print (selected)
    }
    else if( x <= n ){
        for( i in x:(n-y+1) ){
            selected[k-y+1] <<- i
            rec( i+1, y-1 )
        }
    }
}

rec(1,k)
Vinay Lodha
  • 211
  • 2
  • 7