python - How to determine the minimum number to totally break a connected rings? -

it's question on checkio - break rings, can use bad way o(n*2^n) complexity testing possible break ways , find minimum one.

the problem: blacksmith gave apprentice task, ordering them make selection of rings. apprentice not yet skilled in craft , result of this, (to honest, most) of rings came out connected together. he’s asking separating rings , deciding how break enough rings free maximum number of rings possible.

all of rings numbered , told of rings connected. information given sequence of sets. each set describes connected rings. example: {1, 2} means 1st , 2nd rings connected. should count how many rings need break maximum of separate rings. each of rings numbered in range 1 n, n total quantity of rings.

https://static.checkio.org/media/task/media/0d98b24304034e2e9017ba00fc51f6e3/example-rings.svg

example-rings

(sorry don't know how change svg in mac photo.)

in above image can see connections: ({1,2},{2,3},{3,4},{4,5},{4,6},{6,5}). optimal solution here break 3 rings, making 3 full , separate rings. result 3.

input: information connected rings tuple of sets integers.

output: number of rings break integer.

it works when test case small not practical(i guess can't pass test)

from functools import reduce import copy  def break_rings(rings):     max_ring = max(reduce(set.union,rings))     rings = list(rings)     possible_set = [list(bin(i)[2:].rjust(max_ring,'0')) in range(2**max_ring)]     possible_set = [list(map(int,j)) j in possible_set]     min_result = max_ring     test_case in possible_set:         tmp = copy.copy(rings)         tmp2 = copy.copy(rings)         index, value in enumerate(test_case):             if value:                 set_connect in tmp:                     if index+1 in set_connect , set_connect in tmp2:                         tmp2.remove(set_connect)         if not tmp2:             min_result = min(sum(test_case),min_result)     return min_result 

so, think must thinking algorithm graph, don't know kind of problem facing.

can me improve algorithm?

thank looking problem!

you can think of type of graph problem called vertex cover.

draw graph vertex each ring, , edge each connection, i.e. each pair of joined rings.

your task disconnect rings minimum breakages. connection broken if ring @ either edge broken. in other words, need choose set of rings (vertices) such every connection (edge) incident 1 chosen rings.

this vertex cover problem.

unfortunately, vertex cover np-complete there not non-exponential algorithm known.

i recommend improving speed of algorithm rejecting bad cases earlier. example, use backtracking algorithm decides each ring whether break or not. if chose not break it, can conclude lot of other rings must broken.