CODEWITHSUNDEEP
rrecursioncombinatorics
Alexis
Alexis

Reputation: 852

How to enumerate all orderings of n binary objects where k = 1 in R?

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).

Upvotes: 0

Views: 86

Answers (1)

Vinay Lodha
Vinay Lodha

Reputation: 211

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)

Upvotes: 1

Related Questions