r - 尽量减少组数，但将不同组中的敌人分开

Question

我有n=4名为A的个人, B , C和 D .有些人可以属于同一个群体，有些则不能。此信息由以下内容提供(编码为 R )

comparisons =          c("A-B",   "A-C",  "A-D",   "B-C",    "B-D",  "C-D")
areEnemies =           c(FALSE,   FALSE,   TRUE,   FALSE,    FALSE,   TRUE)

根据这些数据，个体 A和 D是敌人，不能属于同一组。个体C和 D敌人也不能属于同一组。所有其他对的个体都是 friend (当你某人不是你的敌人时，那么他(她)就是你的 friend )。

我的目标是创建群组，这样

1. 组数最小化
2. 一个人可以属于一个或多个群体(但必须至少属于一个群体)
3. 如果两个人是敌人，那么他们绝不能属于同一群体。如果两个人是 friend (不是敌人)，那么他们必须至少在同一组中一次。
4. 如果一个人可以属于一个群体，那么它就必须属于这个群体!

上述示例的解决方案(使用小写字母作为组名)是

• A属于组a
• B属于组a和组 b
• C属于组a
• D属于组b

我没能解决这个问题。你能帮我一下吗？

---

如果您想编写代码，我欢迎使用 R、C、C++、Java、Bash、Python，但是对过程(或伪代码)的口头描述已经非常有帮助了。请注意，性能不会太重要，因为我通常只有 5-10 个人，而且不会经常运行此过程。

Answer 1

你所描述的本质上是一个图形问题

数据

library(tidyverse)
df <- tibble(A = c("A", "A", "A", "B", "B", "C"),
        B = c("B", "C", "D", "C", "D", "D"),
        lgl = c(FALSE, FALSE, TRUE, FALSE, FALSE, TRUE))

# A tibble: 6 x 3
  # A     B     lgl  
  # <chr> <chr> <lgl>
# 1 A     B     F    
# 2 A     C     F    
# 3 A     D     T    
# 4 B     C     F    
# 5 B     D     F    
# 6 C     D     T

1 - 从数据框中过滤掉敌人，2 - 然后制作一个无向图(绘制它以查看它)。 3 - 确定图表的 max_cliques。

library(igraph)
data <- filter(df, lgl == FALSE)   # friends
G <- graph_from_data_frame(data, directed=FALSE)
plot(G)
max_cliques(G)

# [[1]]
# + 2/4 vertices, named, from 5940a66:
# [1] D B

# [[2]]
# + 3/4 vertices, named, from 5940a66:
# [1] A B C