Talk:Set consolidation

Why.

I needed this function to find all the ports on a net in an electronic netlist from huge lists of pairs of ports on all the nets of a design. I tried to find out what the "computer science-type" name for the routine might be but failed. --Paddy3118 10:59, 7 May 2012 (UTC)

I'm not sure either, but if you break the sets down into sets of 2, it becomes the problem of finding the connected components of a graph, the sets of size 2 being the edges and the items being the nodes. --Spoon! 18:59, 7 May 2012 (UTC)

Hi Spoon, thanks for the name "Connected components of a graph". It lead to links such as this and this that show that the set consolidation routine in Python could be applied to the type of problems described. --Paddy3118 01:13, 8 May 2012 (UTC)

There's no need to use permutation to show the result is order independent. Think input sets as undirected graph nodes, and two nodes are connected if they share elements, then it's just a matter of finding connected subgraphs which clearly doesn't depend on input set ordering. --Ledrug 23:02, 7 May 2012 (UTC)

Hi Ledrug, I wasn't sure of a general need either so left out mentioning order independence from the main task description but just wanted to make sure of my Python code so reported the run of it in the Python docstring. --Paddy3118 01:13, 8 May 2012 (UTC)

Also task doesn't make clear what should happen when input contains empty sets. Consider this:<lang python>def conso(s):

if len(s) < 2: return s

r, b = [s[0]], conso(s[1:]) for x in b: if r[0].intersection(x): r[0].update(x) else: r.append(x) return r

print(conso([{1, 2}, set([]), set([])]))</lang> Is that what you want? --Ledrug 01:44, 8 May 2012 (UTC)

Cool a recursive version. Maybe you could add it as a second Python implementation? Maybe I need to add that you should return your input when asked to consolidate less than two sets; as you have done. --Paddy3118 10:54, 8 May 2012 (UTC)