Как сгенерировать график, представляющий все возможности, с помощью Python
Мне нужно написать код на Python, который позволит мне сгенерировать дерево возможностей, которые зависят друг от друга. На самом деле, если у нас есть два вектора: a=[0, 1] и b=[0, 1], мы можем построить 4 различных варианта:
(0, 0)(0, 1)(1, 0)(1, 1)
Если мы возьмем (0,0) в качестве родительского узла, мы можем сгенерировать 3 ребра от (0, 0) до всех других возможностей: (0, 0) -> (0, 1), (1, 0), (1, 1).
Затем для каждой возможности мы можем сгенерировать 3 ребра для других возможностей, например:
(0, 1) -> (0, 0), (1, 0), (1, 1)(1, 0) -> (0, 0), (1, 1), (0, 1)(1, 1) -> (0, 0), (1, 0), (0, 1)
Мне нужно повторить это N раз. В результате должно получиться дерево, в котором у каждого нелистового узла есть 3 преемника — для каждой возможности, кроме текущей.
Не могли бы вы уточнить, как (0,1), (1,0) и (1,1) создают одни и те же три набора?
На самом деле (0,1) будет рассматриваться как родитель в своем туре, и принимая во внимание, что первая переменная может быть либо 0, либо 1, и то же самое для второй переменной, мы можем сказать, что (0,1) является одной комбинацией из 4 возможных значений (0,0), (0,1),(1,0),(1,1), но мы исключаем случай, когда он возвращается к себе, поэтому случай (0,1) будет опущен, и поэтому , у нас есть 3 возможных следующих случая ((0,0),(1,0),(1,1)). То же самое для других. Вы хоть представляете, как этого можно добиться????
Ответы 1
Правильное название вашего графика — полный граф. В хороших библиотеках обработки графиков для Python — networkx — есть специальная функция для создания такого типа графиков:
полный_граф
Редактировать 1: Я разработал для вас рабочий процесс, который решает вашу проблему. Вы можете скопировать и вставить его в свой блокнот Jupyter, но обратите внимание, что вам нужно:
- сетьx
- графвиз
- пидот
быть установленным.
import networkx as nx
# Set main parameters
items = {(0, 0), (0, 1), (1, 0), (1, 1)}
root = (0, 1)
N = 4
# Calculate the number of nodes for our tree
node_count = sum((len(items)-1)**i for i in range(N))
# Construct full r-rary tree
G = nx.full_rary_tree(len(items)-1, node_count, create_using=nx.DiGraph)
# Create LG-topologically sorted array of nodes
# NOTE THAT NODES' IDs AREN'T EQUAL TO YOUR ITEMS
lgts = list(nx.lexicographical_topological_sort(G))
# Get the first element to preset its label
first = lgts[0]
# Preset an empty label for all nodes
nx.set_node_attributes(G, '', 'label')
# Set the label for the root
G.nodes[first]['label'] = root
# For all nodes:
for node in lgts:
# Get needed names
s_labels = list(items - {G.nodes[node]['label']})
# For all childs:
for s_node in G.successors(node):
# Set the child's label
G.nodes[s_node]['label'] = s_labels.pop()
# Create dict for drawing labels
labels = {n: G.nodes[n]['label'] for n in G.nodes}
# And draw the final graph
nx.draw(
G,
pos=nx.nx_pydot.graphviz_layout(G, prog='dot'),
with_labels=True,
labels=labels
)
В итоге вы получите этот график:
Спасибо за ваш ответ, похоже на правду, но я хочу, чтобы на каждой итерации система генерировала новые узлы, даже если они уже есть в графе. Итак, с 00 -> 01, 10, 11 все в порядке, но затем для 01 я хочу, чтобы новые узлы представляли 10,11,00
Я не понимаю. Вы хотите построить дерево возможных путей? Потому что, если вы хотите создать узел, равный существующему в графе, они сольются.
Да, я хочу дерево. Подумайте об этом следующим образом: у меня есть 4 комбинации (00,01,10,11), я начинаю с 00 и связываю его с тремя другими узлами, затем каждый раз я беру один из этих узлов и связываю его с тремя другими узлами. , возможно, мне следует каждый раз генерировать новую метку, чтобы у меня были новые узлы, и я повторяю это N раз! Я действительно застрял, есть идеи, пожалуйста
Обновлен ответ для вас.
Большое спасибо, это результат, который я ищу. Еще раз спасибо
Если вы рады моему вопросу, я буду признателен, если вы примете мой ответ.
добро пожаловать в stackoverflow! пожалуйста, возьмите тур, прочитайте как задать вопрос. особенно проявите некоторые усилия в направлении решения.