Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a first list of pairs like this one:

list1= {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {11, 12}, {13, 14}, {15, 16}, {17, 18}, {19, 20}, {21, 22}, {23, 24}, {25, 26}, {27, 28}, {29, 30}, {31, 32}, {33, 34}, {35, 36}, {37, 38}, {39, 40}, {41, 42}, {43, 44}, {45, 46}, {47, 48}, {49, 50}}

And a second one containing information about how the elements of the first list are related:

list2 = {{1, 46}, {5, 27}, {8, 42}, {21, 26, 29}, {31, 45}, {33, 36}, {35, 37}, {47, 49}}

How can I gather elements of the first list using list2 as a reference to get groups like these:

{{{1, 2}, {45, 46}, {31, 32}}, {{5, 6}, {27, 28}}, {{7, 8}, {41, 42}}, {{21, 22}, {25, 26}, {29, 30}}, {{31, 32}, {45, 46}}, {{33, 34}, {35, 36}, {37, 38}}, {{47, 48}, {49, 50}}}

So what it's happening here is that, element {1, 46} of list2 is telling that the pair containing element "1" ({1, 2}) of list1 is linked to element containing element "46" ({45, 46}) and so on.

Note that when you use list 2 element {35, 37} to gather {{35, 36}, {37, 38}} you should consider that list 2 element {33, 36} already linked {{33, 34}, {35, 36}} so you will have a three element group {{33, 34}, {35, 36}, {37, 38}}.

I tried to use graph related functions but couldn't make it work. Any ideas?

share

3 Answers 3

up vote 3 down vote accepted

If I understand your question correctly,

dp = Dispatch@Flatten[{#1 -> {##}, #2 -> {##}} & @@@ list1]

list2 = Sequence @@ Partition[#, 2, 1] & /@ list2

ConnectedComponents@Graph@Union[Sort /@ UndirectedEdge @@@ (list2 /. dp)]

(* ==>

{{{31, 32}, {45, 46}, {1, 2}}, {{21, 22}, {25, 26}, {29, 30}}, {{37, 
   38}, {35, 36}, {33, 34}}, {{41, 42}, {7, 8}}, {{5, 6}, {27, 
   28}}, {{49, 50}, {47, 48}}}

 *)
share
    
This is not the same output you quote. Please check if there's a mistake in the output you posted or whether I misunderstood the question. –  Szabolcs Mar 5 at 1:49
    
Yep, that's totally what I meant. My output is wrong, I'll fix it. –  xtian777x Mar 5 at 1:57
    
@xtian777x Don't be too quick to accept! My code was wrong ;-) I didn't notice the 3-element list in list2. It's fixed now. But it's not pretty. You might consider waiting for a prettier solution :) –  Szabolcs Mar 5 at 2:00
    
Yeah I was coming here to post the error I got. Thanx a lot, that'll work for now. My solution was not even close to be pretty. –  xtian777x Mar 5 at 2:07
    
+1 because my +1 key is stuck... –  rasher Mar 5 at 2:35

Here's a direct list-manipulation approach using a variation of Heike's answer for combining subsets with similar terms:

Cases[list1, {___, Alternatives @@ #, ___}, 2] & /@ list2 //. 
    x_ :> Union @@@ Gather[x, Intersection@## =!= {} &]

(* {{{1, 2}, {31, 32}, {45, 46}}, {{5, 6}, {27, 28}}, {{7, 8}, {41, 42}}, 
    {{21, 22}, {25, 26}, {29, 30}}, {{33, 34}, {35, 36}, {37, 38}}, {{47, 48}, {49, 50}}} *)
share
    
+1, nice and pretty –  rasher Mar 5 at 2:33
c = Cases[list1, {x_,  y_} /; (MatchQ[x, Alternatives @@ #] || 
                               MatchQ[y, Alternatives @@ #]) :> {x, y}] & /@ list2

c //. {x___, {a___, y__, b___}, p___, {c___, y__, d___},  z___} :> {x, {a, y, b, c, d}, p, z}

(*
 {{{1, 2}, {45, 46}, {31, 32}}, 
  {{5, 6}, {27, 28}}, 
  {{7, 8}, {41, 42}}, 
  {{21, 22}, {25, 26}, {29, 30}}, 
  {{33, 34}, {35, 36}, {37, 38}}, 
  {{47, 48}, {49, 50}}}
*)
share
    
Noooooooo! I considered this, but... ReplaceRepeated + multiple BlankNullSequence == kaboom! :D –  rm -rf Mar 5 at 2:30
    
@rm-rf Yep, You preferred copy-pasting Heike's answer. I know –  belisarius Mar 5 at 2:30
    
The joke's still on you buddy, since you copy-pasted my answer =) I'll have a Tantō ready for you. –  rm -rf Mar 5 at 2:32
    
@rm-rf I'm sure I've an older one of mine to cite with the same bad trick –  belisarius Mar 5 at 2:33
    
+1. nice and homely... ;-} –  rasher Mar 5 at 2:34

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .