尽量减少组数，但把敌人分成不同的组。

Question

我有n=4的个人名为A，B，C和D。有些人可以属于同一个群体，而有些人则不能。

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和敌人也不能属于同一群体。所有其他对个人都是朋友(当你的某人不是你的敌人，那么他就是你的朋友)。

我的目标是创建小组

1. 组的数量被最小化。
2. 个人可以属于一个或多个组(但必须至少属于一个组)
3. 如果两个人是敌人，那么他们绝不能是同一群人。如果两个人是朋友(不是敌人)，那么他们必须至少在同一组中一次。
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

Answer 2

#checks if two people are enemies 
def areEnimies(a, b, enemies):
    for x in enemies:
        if (x[0] is a and x[1] is b) or (x[1] is a and x[0] is b):
            return True
    return False

enemies = ["AD", "CD"]  #list of enemies side by side
people = "ABCD" #the list of people who are in the game
groups = []
ans = []
#for each unique enemy, give them there own group
for x in enemies:
    if not x[0] in groups:
        groups.append(x[0])
    if not x[1] in groups:
        groups.append(x[1])
#populate this group with everyone else who is not their enemy
for g in range(len(groups)):
    for p in people:
        if not areEnimies((groups[g])[0], p, enemies) and (groups[g])[0] != p:
            groups[g] += p

#sort each group
for g in range(len(groups)):
    groups[g] = sorted(groups[g])

#if any groups are duplicates of one another we can remove them 
for i in range(len(groups)):
    dup = False
    for j in range(i+1, len(groups)):
        if groups[i] == groups[j]:
            dup = True
            break
    if not dup:
        ans.append(groups[i])

print(ans)

输出= ['A'，'B'，'C'，'B'，'D']

> This is what I came up with
> 1. Write down each unique person that is enemies with someone
> 2. Populate each of those lists with friends 
> 3. Remove duplicate groups if they exist

敌人是由无序成对的，被分成组的人是用字符串表示的，注意，我们不需要朋友的名单，因为任何不是我们可以认为是朋友的敌人的人都不需要。也许有更有效的方法来做到这一点，但对于小团体来说是合理的，我尝试了几种不同的输入。

干杯!

Answer 3

这个问题本质上是一个图论问题。下面是要走的步骤

1. 考虑一下每个朋友之间的优势，而不是敌人之间的优势。
2. 列出所有的集团
3. 移除大团中包含的所有团。
4. 确保没有朋友的顶点也能得到一个群体。

以下是R中的代码

### input data
d <- tibble(A = c("A", "A", "A", "B", "B", "C"),
        B = c("B", "C", "D", "C", "D", "D"),
        friend = c(TRUE, TRUE, FALSE, TRUE, TRUE, FALSE))

### list vertices
vertexes = unique(c(d$from,d$to))

## Create graphs of friends
dFriend = d[d$friend,]
gFriend = graph.data.frame(dFriend, directed=FALSE)

## List all cliques
cliques = lapply(cliques(gFriend), function(x) {names(x)})

## Remove cliques that are contained within other cliques
if (length(cliques))
{
  cliqueIndicesToRemove = c()
  for (i in 1:length(cliques))
  {
    clique_sub = cliques[[i]]
    for (j in 1:length(cliques))
    {
      if (i!=j)
      {
        clique_sup = cliques[[j]]
        if (all(clique_sub %in% clique_sup))
        {
          cliqueIndicesToRemove = c(cliqueIndicesToRemove, i)
        }
      }
    }
  }
  cliques = cliques[-unique(cliqueIndicesToRemove)]
}

## return object
r = tibble(
  cliques   = "",
  vertex    = vertexes   
  )
if (length(cliques))
{
  for (i in 1:length(cliques))
  {
    clique = cliques[[i]]
    matchingVertexes = which(r$vertex %in% clique)
    for (match in matchingVertexes)
    {
      r$cliques[match] = paste0(r$cliques[match], letters[i]  )
    }
  }
}

## Make sure that vertices with no friend still get assigned to a clique
nextLetterIndex = length(cliques) + 1
for (i in 1:nrow(r))
{
  if (r$cliques[i] == "")
  {
    r$cliques[i] = letters[nextLetterIndex]
    nextLetterIndex = nextLetterIndex + 1 
  }
}

这个解决方案很大程度上来自@CPak的回答。