Talk:Set consolidation: Difference between revisions
Content added Content deleted
(→Why.) |
No edit summary |
||
Line 3: | Line 3: | ||
I needed this function to find all the ports on a net in an electronic [[wp:Netlist|netlist]] from huge lists of pairs of ports on all the nets of a design. |
I needed this function to find all the ports on a net in an electronic [[wp:Netlist|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. --[[User:Paddy3118|Paddy3118]] 10:59, 7 May 2012 (UTC) |
I tried to find out what the "computer science-type" name for the routine might be but failed. --[[User:Paddy3118|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. --[[User:Spoon!|Spoon!]] 18: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. --[[User:Spoon!|Spoon!]] 18:59, 7 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. --[[User:Ledrug|Ledrug]] 23:02, 7 May 2012 (UTC) |
Revision as of 23:02, 7 May 2012
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)
- 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)