使用值返回给定顶点集的边值

Question

你目前正试图研究分子的价性质。 这里，化合价是一个原子与其相邻原子连接的键数。精确地说，给定一些正的N个整数，你想知道在满足给定条件的情况下，是否存在原子价数与整数相同的分子

1）每个原子至少由一个键连接，可以有多个键 在两个原子之间

2）分子是连接的，也就是说，分子中每对原子之间都有一条由键组成的路径

3）原子与自身之间没有键

对于给定的N个元素的列表（表示原子的价），您应该返回N乘N矩阵，该矩阵表示原子之间的键数（如果存在这样的分子）。M[i][j]表示原子i和原子j之间的键数。如果这种分子不存在，则不返回必须使用深度优先搜索。

例如，如果给定[20,30,30]，则应返回[[0,10,10]，[10,0,20]，[10,20,0]]。如果给出了[10,10,30]，则返回None

Answer 1

我觉得这个问题很有趣。我提出了一个解决方案，虽然不是深度优先搜索。只是一种暴力手段：

import numpy as np
from itertools import combinations as comb

def findmolecule(v):
    if sum(v) % 2 == 1:
        return None
    n = np.size(v)
    M = np.zeros([n,n])
    total = sum(v)
    varsize = int(n*(n-1)/2)
    for com in comb(range(1,total//2), varsize-1):
        x, y = 0,0
        counter = 0
        partition = [0 for _ in range(varsize)]
        partition[0] = com[0]
        partition[-1] = total//2 - com[-1]
        for i in range(1,varsize-1):
            partition[i] = com[i] - com[i-1]
        while counter < varsize:
            y += 1
            if y == n:
                x += 1
                y = x+1
            M[x,y] = partition[counter]
            M[y,x] = partition[counter]
            counter += 1
        if all(sum(M) == v):
            return M
    return None

matrix = findmolecule([20,30,30])
print(matrix) if matrix is not None else print('None')
matrix = findmolecule([10,10,30])
print(matrix) if matrix is not None else print('None')
matrix = findmolecule([20,32,26,24])
print(matrix) if matrix is not None else print('None')

我只是利用这个事实

1. 矩阵列的和=向量
2. 矩阵是对称的

然后我列出了所有可能的对称矩阵，并检查它们是否满足第一个条件。期待其他解决方案