如何在不生成完整幂集时获取R中指定索引对应的子集

背景 #

我们有一个生成集合幂集的R函数：

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

用它生成3个字母的幂集时，结果符合预期：

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"

但如果要生成26个字母的完整幂集，2^26 = 67108864个元素会直接导致内存不足，无法生成完整列表。不过我们可以生成一个属于该幂集的随机索引，比如13626980，现在需要直接根据这个索引找到对应的字母组合，无需生成完整幂集。

解决方案：利用二进制位映射 #

原函数的幂集生成逻辑基于位运算：每个子集对应一个整数的二进制表示，二进制的每一位标记是否包含对应位置的元素。具体对应关系如下：

• 幂集列表的第k个元素（索引从1开始），对应整数u = k - 1（因为原函数遍历的是0到2^n -1）
• 整数u的二进制每一位，从右到左（最低位到最高位）分别对应集合的第1到第n个元素
• 如果某一位为1，则对应位置的元素包含在子集中；为0则不包含

基于这个逻辑，可以写出直接根据索引获取子集的函数：

index_to_subset <- function(k, set = LETTERS) {
  u <- k - 1
  # 获取u的二进制位（前length(set)位，对应集合每个元素）
  bits <- as.integer(intToBits(u))[1:length(set)]
  # 返回位为1对应的元素
  set[bits == 1]
}

测试与验证 #

• 对于小例子，输入索引6：

index_to_subset(6, LETTERS[1:3])
# 输出：[1] "A" "C"

和原函数生成的results[[6]]完全一致。

• 对于目标索引13626980，直接运行函数：

index_to_subset(13626980)
# 输出：[1] "A" "B" "F" "G" "J" "K" "L" "M" "N" "O" "P" "Q" "R" "S" "V" "W" "Z"

原理说明 #

原函数中masks = 2^(1:n-1)生成的是2^0, 2^1, ..., 2^(n-1)，每个值对应二进制的一位。bitwAnd(u, masks) != 0本质就是判断u的对应二进制位是否为1。我们直接通过intToBits提取二进制位，跳过了生成完整幂集的过程，内存占用极低，即使是26个字母的情况也能瞬间计算。

内容的提问来源于stack exchange，提问作者stats_noob