0

Apologies if the title does not articulate this very well but here is what I'm trying to accomplish:

I have an array of pairs that represent links between the numbers in each pair. I need to derive from this array all the unique groups that the array of pairs represent. Some examples will illustrate this best:

Given:
[0,1]
[1,2]
Result:
[0,1]
[1,2]

Given:
[0,1]
[1,2]
[0,2]
Result:
[0,1,2]

Given:
[0,1]
[1,2]
[1,3]
[2,3]
[2,4]
Result:
[0,1]
[1,2,3]
[2,4]

Just having a hard time trying to wrap my head around the logic needed to accomplish this. Any help would be greatly appreciated (and please edit this post if you think it could be worded better).

zeke
  • 101
  • At the output you want each group to be one that has all its pairs included in the original data? So if the output has $[0,1,2,3]$ the input has to have all six pairs from that set? Do the pairs always have the smaller number first? What should we do with $[0,1],[0,2],[1,2],[1,3],[2,3]?$ We can make $[0,1,2]$ and $[1,2,3]$ but not $[0,1,2,3]$ if I understand correctly. – Ross Millikan Jun 01 '18 at 22:04
  • 2
    It is a bit unclear from your description what exactly it is you want to do, but your examples look like you might be trying to identify maximal cliques in a graph. That is an NP-hard problem. – hmakholm left over Monica Jun 01 '18 at 22:04
  • Or perhaps you're trying to recover a graph from its line graph? If you know that the input will always be a line graph, that looks like it's feasible (with the exception of a few small ambiguous cases). – hmakholm left over Monica Jun 01 '18 at 22:10
  • What is the source of this problem? Is it a programming exercise? – lulu Jun 01 '18 at 22:58
  • "What should we do with [0,1],[0,2],[1,2],[1,3],[2,3]?"

    Yes, result would be: [0,1,2], [1,2,3]

     – zeke Jun 02 '18 at 08:26
  • "What is the source of this problem? Is it a programming exercise?"

    Essentially. I have a program where users can link different components, but they only link two components at a time. I need to show which components are linked together so I'm going to add a colored square to each indicating what is linked to what. So once I have the groups I can then just cycle through colors and assign them to the groups. Some components will have multiple squares if belong to more than one group.

     – zeke Jun 02 '18 at 08:31

0 Answers0