使用 R 中的贝尔数获取集合的所有可能分区

Question

我想找出 R 中多个类别彼此相似的所有可能方式。组合的总数按贝尔数计算。例如。有 15 种方式来组织 4 个类别。

我正在尝试编写一些 R 代码，将这 15 种方式显示为二进制向量。

第一段代码显示有四个 classes，每个都可以取 a、b 或 c 的值。

set.seed(123)
n_classes = 4
classes = LETTERS[1:n_classes]
state = sample(letters[1:3], size = n_classes, replace = TRUE)
# "c" "b" "b" "b"

将每个 class 相互比较，我们可以得到该系统的结构表示：

comparisons = outer(state, state, "==") %>% 
  .[lower.tri(.)]
names(comparisons) = outer(classes, classes, paste0) %>% 
  .[lower.tri(.)]
# > comparisons
# BA    CA    DA    CB    DB    DC 
# TRUE  TRUE FALSE  TRUE FALSE FALSE

可以看到B和A是一样的，C和A也是一样的，所以推导C和B是一样的，其他比较都是不一样的。

我们知道这是四个类别的 15 个解决方案之一 - 我想知道其他 14 个二进制格式的解决方案。

我首先尝试使用 expand.grid，但这并没有说明类别的条件结构（它只是显示了每个单元格为 1 或 0 的所有可能性）

# not correct
poss = rep(list(0:1), length(comparisons))
possibilities = expand.grid(poss)

我觉得有一个简单的解决方案，但我目前对它视而不见。

提前致谢。

Answer 1

您可以使用 R 包 partitions 获取一组类别的所有可能分区。

library(partitions)

# the set to be partitioned
categories <- letters[1:4]

# the clusters defining the partition
clusters <- LETTERS[1:4]

categories |> length() |> listParts()
#> [[1]]
#> [1] (1,2,3,4)
#> 
#> [[2]]
#> [1] (1,2,4)(3)
#> 
#> [[3]]
#> [1] (1,2,3)(4)
#> 
#> [[4]]
#> [1] (1,3,4)(2)
#> 
#> [[5]]
#> [1] (2,3,4)(1)
#> 
#> [[6]]
#> [1] (1,4)(2,3)
#> 
#> [[7]]
#> [1] (1,2)(3,4)
#> 
#> [[8]]
#> [1] (1,3)(2,4)
#> 
#> [[9]]
#> [1] (1,4)(2)(3)
#> 
#> [[10]]
#> [1] (1,2)(3)(4)
#> 
#> [[11]]
#> [1] (1,3)(2)(4)
#> 
#> [[12]]
#> [1] (2,4)(1)(3)
#> 
#> [[13]]
#> [1] (2,3)(1)(4)
#> 
#> [[14]]
#> [1] (3,4)(1)(2)
#> 
#> [[15]]
#> [1] (1)(2)(3)(4)
categories |> length() |> setparts()
#>                                   
#> [1,] 1 1 1 1 2 1 1 1 1 1 1 2 2 2 1
#> [2,] 1 1 1 2 1 2 1 2 2 1 2 1 1 3 2
#> [3,] 1 2 1 1 1 2 2 1 3 2 1 3 1 1 3
#> [4,] 1 1 2 1 1 1 2 2 1 3 3 1 3 1 4
categories |>
  length() |>
  setparts() |>
  as.matrix() |>
  as.data.frame() |>
  lapply(function(x) sapply(x, function(y) clusters[[y]])) |>
  as.data.frame()
#>   V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15
#> 1  A  A  A  A  B  A  A  A  A   A   A   B   B   B   A
#> 2  A  A  A  B  A  B  A  B  B   A   B   A   A   C   B
#> 3  A  B  A  A  A  B  B  A  C   B   A   C   A   A   C
#> 4  A  A  B  A  A  A  B  B  A   C   C   A   C   A   D

^{由 reprex package (v2.0.0)}

于 2022-05-16 创建

使用 R 中的贝尔数获取集合的所有可能分区

Get all possible partitions of a set using Bell's number in R

r

combinations