Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Random Hamiltonian cycle solution in Clear category for Family Gifts by vinc
from collections import defaultdict
from itertools import combinations
from random import sample
def find_chains(family: set, couples: tuple):
# build a family's graph
graph = defaultdict(set)
for v1,v2 in combinations(family, 2):
if {v1,v2} not in couples:
graph[v1].add(v2)
graph[v2].add(v1)
# find only ONE Hamiltonian cycle in the graph with DFS
def explore(v, path):
for child in graph[v]:
if (v, child) not in gifted:
if len(path) == len(graph) and child == start:
gifted.update(zip(path, path[1:] + [path[0]]))
return path
elif child not in path:
new_path = explore(child, path + [child])
if new_path:
return new_path
return None
# take an arbitrary vertex and find the Hamiltonian cycle for each of its neighbors
result = []
for start in sample(family, len(family)):
gifted = set()
chains = []
for child in sample(graph[start], len(graph[start])):
chain = explore(child, [start, child])
if chain:
chains.append(chain)
if len(chains) > len(result):
result = chains
return result
Sept. 1, 2017
