Комбинаторика в Python

У меня есть своего рода одноуровневая древовидная структура:

альтернативный текст

Где p — родительские узлы, c — дочерние узлы, а b — гипотетические ветви.

Я хочу найти все комбинации ветвей с ограничением, что только один родитель может разветвляться только на один дочерний узел, а две ветви не могут совместно использовать Родитель и/или ребенок.

Например. если combo это набор комбинаций:

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

Думаю, это все. знак равно

Как это может быть достигнуто автоматически в Python для произвольных деревьев этих структур, т.е. количество p:s, c:s и b:s произвольно.

РЕДАКТИРОВАТЬ:

Это не дерево, а скорее двудольный ориентированный ациклический граф


python directed-acyclic-graphs combinatorics bipartite
person Theodor    schedule 04.11.2010    source источник
comment
Ваше изображение предполагает, что есть ветви, доступные от каждого родителя к каждому ребенку. Вы предполагаете это?   -  person dhill    schedule 04.11.2010
comment
У вас уже есть структура данных для представления этого?   -  person Björn Pollex    schedule 04.11.2010
comment
@dhill - Правда? Родительский узел p1 не разветвляется на дочерний узел c0.   -  person Theodor    schedule 04.11.2010
comment
Кроме того, это не дерево, а двудольный DAG.   -  person Björn Pollex    schedule 04.11.2010
comment
@Space_C0wb0y - А что теперь? Пожалуйста, вставьте ссылку на Википедию или аналогичную. ;) Что касается структуры данных, рассмотрите b как объект с переменными p и c, такими как b[0].p = 0.   -  person Theodor    schedule 04.11.2010
comment
@Theodor: я имел в виду двусторонний ориентированный ациклический граф.   -  person Björn Pollex    schedule 04.11.2010
comment
@ Space_C0wb0y - согласен, это то, что есть. Я отредактирую.   -  person Theodor    schedule 04.11.2010
comment
Я действительно запутался: в вашем примере ветки b3 и b2 имеют одни и те же родительские и дочерние элементы, что противоречит правилу, согласно которому две ветви не могут иметь общих родительских и/или дочерних элементов. Есть возможность обновить графику?   -  person Richard Green    schedule 04.11.2010
comment
@Richard - ветви на графике являются гипотетическими ветвями. Я добавлю это в вопрос.   -  person Theodor    schedule 04.11.2010
comment
@Richard b3 и b2 имеют зеркальные родительские и дочерние элементы. О чем ты говоришь?   -  person aaronasterling    schedule 04.11.2010
comment
Какое программное обеспечение вы использовали для создания сюжета?   -  person Muhammad Alkarouri    schedule 10.11.2010
comment
@Muhammad - MS Visio 2010. Если вы студент, вы иногда можете получить бесплатную студенческую лицензию в MSDN.   -  person Theodor    schedule 11.11.2010

Ответы (2)


arrow_upward
5
arrow_downward

Вот один из способов сделать это. Можно сделать множество микрооптимизаций, но их эффективность будет зависеть от задействованных размеров.

import collections as co
import itertools as it

def unique(list_):
    return len(set(list_)) == len(list_)

def get_combos(branches):
    by_parent = co.defaultdict(list)

    for branch in branches:
        by_parent[branch.p].append(branch)

    combos = it.product(*by_parent.values())

    return it.ifilter(lambda x: unique([b.c for b in x]), combos)

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

person aaronasterling    schedule 04.11.2010
comment
Я думаю, вы имели в виду, что аргумент для get_combos должен быть ветвями, иначе для ветвей в ветвях будет выдано исключение. - person Philip Starhill; 04.11.2010
comment
@Philip Хорошо выглядишь. Фиксированный. - person aaronasterling; 04.11.2010
comment
Большое спасибо, отличное решение! - person Theodor; 04.11.2010
comment
что такое branches? какой тип питона? какое содержание? - person dbliss; 02.09.2015
comment
^ теперь я вижу, что об этом говорится в комментариях. тем не менее, было бы неплохо указать это в ответе. - person dbliss; 02.09.2015

arrow_upward
4
arrow_downward

Посмотрите на комбинаторные генераторы itertools:

  • товар()
  • перестановки ()
  • комбинации()
  • комбинации_с_заменой()

Похоже, вы можете написать итератор для достижения того, чего хотите.

person Paulo Scardine    schedule 04.11.2010