Selecting Elements from a List that Doesn't Exist?

[omario]

I found this function in R that can return the "power set" for a set of letters:

f <- function(set) { 
  n <- length(set)
  masks <- 2^(1:n-1)
  lapply( 1:2^n-1, function(u) set[ bitwAnd(u, masks) != 0 ] )
}

results = f(LETTERS[1:3])

[[1]]
character(0)

[[2]]
[1] "A"

[[3]]
[1] "B"

[[4]]
[1] "A" "B"

[[5]]
[1] "C"

[[6]]
[1] "A" "C"

[[7]]
[1] "B" "C"

[[8]]
[1] "A" "B" "C"

As an example, suppose I were to generate some random sequence of letters:

> random = sample.int(length(results), 1)
[1] 6

> results[random]
[[1]]
[1] "A" "C"

Suppose now I want to make a list of the power set for all 26 letters: I know that this list would have 2^26 = 67108864 elements. There is no way that I would be able to store such a large list in the local R environment!

# too big
big_results = f(LETTERS[1:26])

But suppose I were to generate some random number:

big_random = sample.int(67108864, 1)

13626980

• Is there some way of knowing which permutation of letters the "big_random" would correspond to on the "big_results" list - without actually fully running "big_results"?

For example:

# too big to run (hypothetical list)
big_results[big_random]

• Could some enumeration or recursion formula be used to figure out some pattern and then somehow determine that "13626980" corresponds to the letters "P H R T L D U Z" for instance?

Thank you!

[AlexisW]

I don't fully understand how the function works, what with that bitwAnd(), but its structure is relatively clear: the lapply() acts as a loop to generate the result. So you can easily avoid running the lapply() and only compute it's second argument for a given value of u.