алгоритм для группировки элементов в группах 3

Question

Я пытаюсь решить проблему, где у меня есть пары, как:

A C 
B F 
A D 
D C 
F E 
E B 
A B 
B C 
E D 
F D 

и мне нужно сгруппировать их в группы по 3, где я должен иметь triangule согласования с этот список. В принципе, мне нужен результат, если это возможно или нет, чтобы сгруппировать коллекцию.

Таким образом, возможные группы (ACD и BFE), или (ABC и DEF) и эта коллекция, так как все групповая письма могут быть сгруппированы в группы по 3 и ни один не остается вне.

Я сделал сценарий, где я могу достичь этого для небольших объёмов ввода, но для больших объёмов он становится слишком медленным.

Моя логика:

make nested loop to find first match (looping untill I find a match) 
> remove 3 elements from the collection 
    > run again 

и я делаю это, пока я не из букв. Поскольку могут быть разные комбинации, я запускаю это несколько раз, начиная с разных букв, пока не найду совпадение.

Я могу понять, что это дает мне петли по порядку как минимум N^N и может быть слишком медленным. Есть ли лучшая логика для таких проблем? может ли здесь использоваться двоичное дерево?

Answer 1

Эта проблема может быть смоделирована как график Clique cover problem. Каждая буква - это узел, а каждая пара - это ребро, и вы хотите разбить график на vertex-disjoint клики размером 3 (треугольники). Если вы хотите, чтобы разбиение было минимальным, то вы хотите, чтобы минимальная кликовая обложка .
На самом деле это была бы проблема с обложкой k-clique, потому что в проблеме обложки клики вы можете иметь клики произвольных/разных размеров.

Answer 2

Как уже указывал Альберто Ривелли, эта проблема сводима к Clique Cover problem, которая является NP-твердой. Это также сводится к проблеме нахождения клики конкретного/максимального размера. Возможно, есть и другие, а не NP-жесткие проблемы, к которым ваш конкретный случай можно было бы свести, но я не думал ни о чем.

Однако существуют do существуют алгоритмы, которые могут найти решение в полиномиальное время, хотя и не всегда для худших случаев. Один из них - Bron–Kerbosch algorithm, который, как известно, является самым эффективным алгоритмом для нахождения максимальной клики и может найти клику в худшем случае O (3^(n/3)). Я не знаю размер ваших материалов, но надеюсь, этого будет достаточно для вашей проблемы.

Вот код в Python, готовый пойти:

#!/usr/bin/python3 
# @by DeFazer 
# Solution to: 
# stackoverflow.com/questions/40193648/algorithm-to-group-items-in-groups-of-3 
# Input: 
# N P - number of vertices and number of pairs 
# P pairs, 1 pair per line 
# Output: 
# "YES" and groups themselves if grouping is possible, and "NO" otherwise 
# Input example: 
# 6 10 
# 1 3 
# 2 6 
# 1 4 
# 4 3 
# 6 5 
# 5 2 
# 1 2 
# 2 3 
# 5 4 
# 6 4 
# Output example: 
# YES 
# 1-2-3 
# 4-5-6 
# Output commentary: 
# There are 2 possible coverages: 1-2-3*4-5-6 and 2-5-6*1-3-4. 
# If required, it can be easily modified to return all possible groupings rather than just one. 

# Algorithm: 
# 1) List *all* existing triangles (1-2-3, 1-3-4, 2-5-6...) 
# 2) Build a graph where vertices represent triangles and edges connect these triangles with no common... vertices. Sorry for ambiguity. :) 
# 3) Use [this](en.wikipedia.org/wiki/Bron–Kerbosch_algorithm) algorithm (slightly modified) to find a clique of size N/3. 
#  The grouping is possible if such clique exists. 

N, P = map(int, input().split()) 
assert (N%3 == 0) and (N>0) 
cliquelength = N//3 

pairs = {} # {a:{b, d, c}, b:{a, c, f}, c:{a, b}...} 

# Get input 

# [(0, 1), (1, 3), (3, 2)...] 
##pairlist = list(map(lambda ab: tuple(map(lambda a: int(a)-1, ab)), (input().split() for pair in range(P)))) 
pairlist=[] 
for pair in range(P): 
    a, b = map(int, input().split()) 
    if a>b: 
     b, a = a, b 
    a, b = a-1, b-1 
    pairlist.append((a, b)) 
pairlist.sort() 

for pair in pairlist: 
    a, b = pair 

    if a not in pairs: 
     pairs[a] = set() 
    pairs[a].add(b) 

# Make list of triangles 
triangles = [] 
for a in range(N-2): 
    for b in pairs.get(a, []): 
     for c in pairs.get(b, []): 
      if c in pairs[a]: 
       triangles.append((a, b, c)) 
       break 

def no_mutual_elements(sortedtupleA, sortedtupleB): 
    # Utility function 
    # TODO: if too slow, can be improved to O(n) since tuples are sorted. However, there are only 9 comparsions in case of triangles. 
    return all((a not in sortedtupleB) for a in sortedtupleA) 

# Make a graph out of that list 
tgraph = [] # if a<b and (b in tgraph[a]), then triangles[a] has no common elements with triangles[b] 
T = len(triangles) 
for t1 in range(T): 
    s = set() 
    for t2 in range(t1+1, T): 
     if no_mutual_elements(triangles[t1], triangles[t2]): 
      s.add(t2) 
    tgraph.append(s) 

def connected(a, b): 
    if a > b: 
     b, a = a, b 
    return (b in tgraph[a]) 

# Finally, the magic algorithm! 

CSUB = set() 
def extend(CAND:set, NOT:set) -> bool: 
    # while CAND is not empty and there is no vertex in NOT connected to *all* vertexes in CAND 
    while CAND and all((any(not connected(n, c) for c in CAND)) for n in NOT): 
     v = CAND.pop() 
     CSUB.add(v) 
     newCAND = {c for c in CAND if connected(c, v)} 
     newNOT = {n for n in NOT if connected(n, v)} 
     if (not newCAND) and (not newNOT) and (len(CSUB)==cliquelength): # the last condition is the algorithm modification 
      return True 
     elif extend(newCAND, newNOT): 
      return True 
     else: 
      CSUB.remove(v) 
      NOT.add(v) 

if extend(set(range(T)), set()): 
    print("YES") 
    # If the clique itself is not needed, it's enough to remove the following 2 lines 
    for a, b, c in [triangles[c] for c in CSUB]: 
     print("{}-{}-{}".format(a+1, b+1, c+1)) 
else: 
    print("NO") 

Если это решение еще слишком медленно, perphaps может быть более эффективным, чтобы решить эту проблему Clique Cover вместо. Если это так, я могу попытаться найти для него правильный алгоритм.

Надеюсь, что это поможет!

Answer 3

Ну, я реализовал работу в JS, где я чувствую себя наиболее уверенно. Я также пробовал 100000 ребер, которые случайным образом выбираются из 26 букв. При условии, что все они уникальны, а не такие, как ["A",A"], он разрешается через 90 ~ 500 мс. Самая сложная часть заключалась в том, чтобы получить неидентичные группы, без изменения порядка треугольников.Для данных данных ребер разрешается в течение 1 мс.

В качестве краткого изложения первая ступень снижения показывает, что треугольники и вторая группа уменьшают группу отключенных.

function getDisconnectedTriangles(edges){ 
 
return edges.reduce(function(p,e,i,a){ 
 
         var ce = a.slice(i+1) 
 
           .filter(f => f.some(n => e.includes(n))), // connected edges 
 
          re = [];          // resulting edges 
 
         if (ce.length > 1){ 
 
         re = ce.reduce(function(r,v,j,b){ 
 
              var xv = v.find(n => e.indexOf(n) === -1), // find the external vertex 
 
               xe = b.slice(j+1)      // find the external edges 
 
                .filter(f => f.indexOf(xv) !== -1); 
 
              return xe.length ? (r.push([...new Set(e.concat(v,xe[0]))]),r) : r; 
 
             },[]); 
 
         } 
 
         return re.length ? p.concat(re) : p; 
 
        },[]) 
 
      .reduce((s,t,i,a) => t.used ? s 
 
             : (s.push(a.map((_,j) => a[(i+j)%a.length]) 
 
                .reduce((p,c,k) => k-1 ? p.every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, p.push(c),p) : p 
 
                      : [p].every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, [p,c]) : [p])),s) 
 
            ,[]); 
 
} 
 

 
var edges = [["A","C"],["B","F"],["A","D"],["D","C"],["F","E"],["E","B"],["A","B"],["B","C"],["E","D"],["F","D"]], 
 
     ps = 0, 
 
     pe = 0, 
 
    result = []; 
 

 
ps = performance.now(); 
 
result = getDisconnectedTriangles(edges); 
 
pe = performance.now(); 
 
console.log("Disconnected triangles are calculated in",pe-ps, "msecs and the result is:"); 
 
console.log(result);

Вы можете генерировать случайные ребра различной длины и играть с кодом here