Minimize the number of groups, but separate the enemies in different groups

Question

I have the n=4individuals named A, B, Cand D. Some people may belong to the same group, and some may not. This information is specified as follows (encoded in R)

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

From these data, individuals Aand Dare enemies and can not belong to the same group. Persons Cand Denemies cannot belong to the same groups. All other pairs of people are friends (when you someone is not your enemy, then he is your friend).

My goal is to create groups to

• The number of groups is minimized
• A person can belong to one or several groups (but must belong to at least one group)
• If two people are enemies, they should never be in the same group. If two people are friends (not enemies), then they must be in the same group at least once.
• If a person can belong to a group, then he must!

The solution (using lowercase letters for group names) for the above example is

• A belongs to the group A
• Bbelongs to group Aand groupB
• C belongs to the group A
• D belongs to the group B

I can’t wrap my head around this problem. Can you give me a hand?

---

If you want to write code, I welcome R, C, C ++, Java, Bash, Python, but a verbal description of the process (or pseudocode) will already be very useful. Please note that performance will not make much difference, as I usually have only 5-10 people and will not start this process too often.

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)

output = [['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

- . ,

• , .
• cliques
• , .
• Make sure that vertices that don't have a friend also get a group.

Here is the code in 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 
  }
}

This solution was very inspired by @CPack's answer.