Вернуть значение ребер из заданного набора вершин со значением

Question

В настоящее время вы пытаетесь исследовать свойство валентности в молекуле. Здесь валентность - это число связей, соединяющих атом с соседними атомами. Точно говоря, учитывая некоторые положительные N целых чисел, вы хотите знать, может ли существовать молекула, у которой валентные числа атомов одинаковы с целыми числами при соблюдении заданных условий.

1) Каждый атом соединен по крайней мереодна связь, и между двумя атомами может быть несколько связей.

2) Молекула связана, то есть существует путь, состоящий из связей между каждой парой атомов в молекуле.

3) Нет связи между атомом и самим собой.

Для данного списка (который представляет валентность атомов) из N элементов, вы должны вернуть матрицу N by N, которая представляет количество связей между атомами, если таковыемолекула существует. M [i] [j] означает число связей между атомом i и атомом j. Если такая молекула не может существовать, верните None. Вы должны использовать поиск в глубину.

Например, если задано [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. матрица симметрична

Затем я перечислил все возможные симметричные матики и проверил, удовлетворяют ли они первому условию. С нетерпением ждем других решений!