-2

I'm having trouble with a simple but difficult problem.

My goal is to find connectivity of 3d geometry. Simplified, I want to combine sublists if they share common elements.

  • Here is my list: [[3, 0], [0, 9], [9, 13], [7, 4]]
  • And what I want to return is: [[0, 3, 9, 13], [7, 4]]

I thought it is simple, but I cannot figure it out. Thank you!

Swifty
  • 2,630
  • 2
  • 3
  • 21
bsjun
  • 37
  • 1
  • 8
  • 2
    Hmmm, if I understand correctly, you want to **merge** sublists if they **have common elements** ? If I'm right, please update your question to make it clearer. In addition, please include the code you already tried. – Swifty Aug 22 '23 at 07:40
  • 2
    Does this answer your question? [Merge lists that share common elements](https://stackoverflow.com/questions/4842613/merge-lists-that-share-common-elements) – Swifty Aug 22 '23 at 07:42
  • What is supposed to happen, if the new list to merge has common elements with more than one existing list? Or can't this happen? – guidot Aug 22 '23 at 07:46
  • @Swifty Corrects! Thank you so much! – bsjun Aug 22 '23 at 07:57
  • 2
    Why is the first element in the required output [0,3,9,13] rather than [3,0,9,13]? What's the logic behind that? It's obviously not sorted because of [7,4] – DarkKnight Aug 22 '23 at 08:13
  • Does remind me of the Minimal Spanning tree problem of Kruskal which merges sets. Maybe that algorithm gives you some ideas. – Daraan Aug 22 '23 at 08:17

1 Answers1

1

You could use an intermediate dictionary that associates common sets to each value. Then extract the list of sets converting them to lists:

L  = [[3, 0], [0, 9], [9, 13], [7, 4]]

merged = dict()
for sublist in L:
    mSet = set().union(sublist,*filter(None,map(merged.get,sublist)))
    for value in mSet:
         merged[value] = mSet
*result, = map(list,{id(s):s for s in merged.values()}.values())

print(result)

[[0, 3, 9, 13], [4, 7]]

Note: This does not preserve the original order within each sublist. It also assumes that values are already unique within each list and will not preserve duplicates if there were any. If order or duplicates need to be preserved, a similar (albeit more involved) solution could be used. Please say so in your question if that is the case

Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • Nice one; I had thought of making some dict {value: [sublist indexes]} but didn't dig deeper. – Swifty Aug 22 '23 at 14:05