Python Combinatorics, часть 2

Question

Это дополнительный вопрос к Комбинаторика в Python

У меня есть дерево или направленный ациклический граф, если вы будете иметь структуру как:

Где r - корневые узлы, p - родительские узлы, c - дочерние узлы, а b - гипотетические ветви. Корневые узлы не связаны напрямую с родительскими узлами, это всего лишь ссылка.

Я заинтересован в нахождении всех комбинаций ветвей при ограничениях:

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

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

combo[0] = [b[0], b[1], b[2], b[3]]
combo[1] = [b[0], b[1], b[2], b[4]]

Структура данных такова, что b представляет собой список объектов ветвей, которые имеют свойства r, c и p, например ::

b[3].r = 1
b[3].p = 3
b[3].c = 2

Answer 1

Эта проблема может быть решена в Python легко и элегантно, потому что есть модуль, называемый "itertools".

Допустим, у нас есть объекты типа HypotheticalBranch, которые имеют атрибуты r, p и c. Как вы описали в своем посте:

class HypotheticalBranch(object):
  def __init__(self, r, p, c):
    self.r=r
    self.p=p
    self.c=c
  def __repr__(self):
    return "HypotheticalBranch(%d,%d,%d)" % (self.r,self.p,self.c)

Ваш набор гипотетических ветвей, таким образом,

b=[ HypotheticalBranch(0,0,0),
  HypotheticalBranch(0,1,1),
  HypotheticalBranch(1,2,1),
  HypotheticalBranch(1,3,2),
  HypotheticalBranch(1,4,2) ]

Магическая функция, которая возвращает список всех возможных комбинаций ветвей, может быть написана так:

import collections, itertools

def get_combos(branches):
  rc=collections.defaultdict(list)
  for b in branches:
    rc[b.r,b.c].append(b)
  return itertools.product(*rc.values())

Если быть точным, эта функция возвращает итератор. Получить список, перебирая его. Эти четыре строки кода выведут все возможные комбинации:

for combo in get_combos(b):
  print "Combo:"
  for branch in combo:
    print "  %r" % (branch,)

Вывод этой программы:

Combo:
  HypotheticalBranch(0,1,1)
  HypotheticalBranch(1,3,2)
  HypotheticalBranch(0,0,0)
  HypotheticalBranch(1,2,1)
Combo:
  HypotheticalBranch(0,1,1)
  HypotheticalBranch(1,4,2)
  HypotheticalBranch(0,0,0)
  HypotheticalBranch(1,2,1)

... это именно то, что вы хотели.

Так что же делает скрипт? Он создает список всех гипотетических ветвей для каждой комбинации (корневой узел, дочерний узел). И затем он дает произведение этих списков, то есть все возможные комбинации одного элемента из каждого из списков.

Я надеюсь, что получил то, что вы на самом деле хотели.

Answer 2

Здесь действительно две проблемы: во-первых, вам нужно разработать алгоритм, который вы будете использовать для решения этой проблемы, и, во-вторых, вам нужно его реализовать (в Python).

---

Алгоритм

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

Следовательно, для дочернего узла мы хотим взять как можно больше ветвей, при условии ограничения, что никакие два родительских узла не имеют общего корня. Другими словами, у каждого ребенка у вас может быть не более одного ребра в окрестности каждого корневого узла. Кажется, это говорит о том, что вы хотите выполнить итерации сначала по дочерним элементам, а затем по (окрестностям) корневых узлов и, наконец, по ребрам между ними. Эта концепция дает следующий псевдокод:

for each child node:
    for each root node:
        remember each permissible edge

find all combinations of permissible edges

---

Код

>>> import networkx as nx
>>> import itertools
>>> 
>>> G = nx.DiGraph()
>>> G.add_nodes_from(["r0", "r1", "p0", "p1", "p2", "p3", "p4", "c0", "c1", "c2"])
>>> G.add_edges_from([("r0", "p0"), ("r0", "p1"), ("r1", "p2"), ("r1", "p3"),
...                   ("r1", "p4"), ("p0", "c0"), ("p1", "c1"), ("p2", "c1"),
...                   ("p3", "c2"), ("p4", "c2")])
>>> 
>>> combs = set()
>>> leaves = [node for node in G if not G.out_degree(node)]
>>> roots = [node for node in G if not G.in_degree(node)]
>>> for leaf in leaves:
...     for root in roots:
...         possibilities = tuple(edge for edge in G.in_edges_iter(leaf)
...                               if G.has_edge(root, edge[0]))
...         if possibilities: combs.add(possibilities)
... 
>>> combs
set([(('p1', 'c1'),), 
     (('p2', 'c1'),), 
     (('p3', 'c2'), ('p4', 'c2')), 
     (('p0', 'c0'),)])
>>> print list(itertools.product(*combs))
[(('p1', 'c1'), ('p2', 'c1'), ('p3', 'c2'), ('p0', 'c0')), 
 (('p1', 'c1'), ('p2', 'c1'), ('p4', 'c2'), ('p0', 'c0'))]

Кажется, вышеприведенное работает, хотя я не проверял.

Answer 3

Второе ограничение означает, что вам нужны максимальные комбинации, т. Е. Все комбинации, длина которых равна наибольшей комбинации.

Я бы подошел к этому, пройдя сначала структуру «b» и создав структуру с именем «c» для хранения всех ветвей, приходящих к каждому дочернему узлу и классифицированных по корневому узлу, который к нему приходит.

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

Например, ваша структура "c" будет выглядеть так:

c[i][j] = [b_k0, ...]  
--> means c_i has b_k0, ... as branches that connect to root r_j)

Для приведенного вами примера:

c[0][0] = [0]
c[0][1] = []
c[1][0] = [1]
c[1][1] = [2]
c[2][0] = []
c[2][1] = [3, 4]

Это должно быть довольно легко закодировать с использованием этого подхода. Вам просто нужно перебрать все ветви "b" и заполнить структуру данных для "c". Затем напишите небольшую рекурсивную функцию, которая просматривает все элементы внутри «c».

Вот код (я ввел ваши данные в качестве примера для тестирования):

class Branch:
  def __init__(self, r, p, c):
    self.r = r
    self.p = p
    self.c = c

b = [
    Branch(0, 0, 0),
    Branch(0, 1, 1),
    Branch(1, 2, 1),
    Branch(1, 3, 2),
    Branch(1, 4, 2)
    ]

total_b = 5   # Number of branches
total_c = 3   # Number of child nodes
total_r = 2   # Number of roots

c = []
for i in range(total_c):
  c.append([])
  for j in range(total_r):
    c[i].append([])

for k in range(total_b):
  c[b[k].c][b[k].r].append(k)

combos = []
def list_combos(n_c, n_r, curr):
  if n_c == total_c:
    combos.append(curr)
  elif n_r == total_r:
    list_combos(n_c+1, 0, curr)
  elif c[n_c][n_r]:
      for k in c[n_c][n_r]:
        list_combos(n_c, n_r+1, curr + [b[k]])
  else:
    list_combos(n_c, n_r+1, curr)

list_combos(0, 0, [])

print combos

Answer 4

Для каждого ребенка c, с гипотетическими родителями p (c), с корнями r (p (c)), выберите ровно одного родителя p из p (c) для каждого корня r в r (p (c)) (например, что r является корнем из p) и включает b в комбинацию, где b соединяет p с c (при условии, что есть только один такой b, то есть это не мультиграф). Количество комбинаций будет являться произведением числа родителей, по которому каждый ребенок гипотетически связан с каждым корнем. Другими словами, размер набора комбинаций будет равен произведению гипотетических связей всех дочерне-корневых пар. В вашем примере все такие пары потомок-корень имеют только один путь, кроме r1-c2, который имеет два пути, поэтому размер набора комбинаций равен двум.

Это удовлетворяет условию отсутствия комбинации, являющейся подмножеством другой, поскольку, выбирая ровно одного родителя для каждого корня каждого дочернего элемента, мы максимизируем число соединений. Впоследствии добавление любого ребра b приведет к тому, что его корень будет дважды связан с дочерним, что недопустимо. А поскольку мы выбираем ровно одну, все комбинации будут одинаковой длины.

Рекурсивная реализация этого выбора даст желаемые комбинации.