python - 如何在图上找到一组元素的所有唯一排列

我有一个 Material 科学问题，我可以肯定可以使用networkx解决，但是我不确定如何解决。

首先，我想找到3个元素的所有唯一组合，并进行替换。我已经使用itertools完成了如下操作:

elements = ["Mg","Cu","Zn"]
combinations = list(itertools.combinations_with_replacement(elements, 3))

对于这些组合中的每一个，我都希望在一个简单的图上找到所有唯一的排列。该图具有三个节点和三个边，其中每个节点都连接到另外两个节点。重要的是，这些边的距离为1，但是其中一个边的距离为2。基本上，像一个直角三角形一样。

例如类似于Node1 Node2 Node3 Node1

因此，对于组合[“Mg”，“Cu”，“Cu”]，应该有两个唯一的排列:

a)Mg(站点1)-1- Cu(站点2)-1- Mg(站点3)-2- Mg(站点1)
b)Mg(位点1)-1- Mg(位点2)-1- Cu(位点3)-2- Mg(位点1)
c)Cu(site1)-1- Mg(site2)-1- Mg(site3)-2- Cu(site1)(与b相同)

注意:我不确定定义图的最佳方法，可能是这样的:

import networkx as nx
FG = nx.Graph()
FG.add_weighted_edges_from([(1, 2, 1), (2, 3, 1), (3, 1, 2)])

最佳答案

您要使用的唯一性标准称为graph isomorphism。 NetworkX有一个子模块:networkx.algorithms.isomorphism。您可以使用node_match/edge_match参数指定将图的节点/边精确地视为“相等”的程度。这是示例:

import networkx as nx

FG1 = nx.Graph()
FG1.add_node(1, element='Cu')
FG1.add_node(2, element='Cu')
FG1.add_node(3, element='Mg')
FG1.add_weighted_edges_from([(1, 2, 1), (2, 3, 1), (3, 1, 2)])

FG2 = nx.Graph()
FG2.add_node(1, element='Cu')
FG2.add_node(2, element='Mg')
FG2.add_node(3, element='Cu')
FG2.add_weighted_edges_from([(1, 3, 1), (2, 3, 1), (1, 2, 2)])

nx.is_isomorphic(
    FG1,
    FG2,
    node_match=lambda n1, n2: n1['element'] == n2['element'],
    edge_match=lambda e1, e2: e1['weight'] == e2['weight']
)

True
如果要重命名任何元素或更改任何边缘权重，则图形将变为非同构(带有这些参数)。这样便可以找到唯一的图-非同构图的集合。请注意，图形同构问题在计算上非常繁重，因此即使对于中等大小的图形也不应使用它。

但是您的任务有很多限制，因此不需要使用图形。如果“分子”中只有3个元素，则元素组合只有3种类型:

1-1-1

1-1-2

1-2-3

对于它们中的每一个，您可以计算并说明唯一组合的数量:
1-1-1:一个-1=1-11-1-2:两个-1=1-2和1-1=21-2-3:三种-1=2-3，1-2=3和1-2-3(=1)
因此，您可以将每个itertools-combination乘以可能的组合数:

number_of_molecular_combinations = 0
for c in combinations:
    number_of_molecular_combinations += len(set(c))
print(number_of_molecular_combinations)

18
该方法比图形处理更快地运行FAR，但仅在像您这样的非常严格的限制条件下可用。

关于python - 如何在图上找到一组元素的所有唯一排列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60377332/