Re: a tricky List manipulation problem
- To: mathgroup at smc.vnet.net
- Subject: [mg16324] Re: [mg16211] a tricky List manipulation problem
- From: BobHanlon at aol.com
- Date: Sun, 7 Mar 1999 01:05:46 -0500
- Sender: owner-wri-mathgroup at wolfram.com
In a message dated 3/5/99 4:58:47 AM, hanssen at zeiss.de writes:
>suppose I have two lists of lists which are structured like this:
>
>l1={{s1,x1},....,{si,xi}},
>l2={{t1,y1},....,{tk,yk}}.
>
>where the lengths of the two lists may be different. The first
>entries in the lists serve als "Tags", the second are "values".
>Suppose, no tag appears twice in l1 or twice in l2.
>
>I am looking for the list of elements {sh,xh,yh} of elements
>with the following conditions:
>
>{sh,xh} is element of l1 AND
>{sh,yh] is element of l2 (i.e. combine elements with same "tag")
>
>Without loss of generality suppose, both lists are sorted by their tags.
>
>A procedural approach to this problem would be to climb
>down the ladder starting with {i,j}={1,1}, comparing pairs l1[[i,1]] and
>l2[[j,1]]
>and taking found tag matches to a result list. This requires some caution,
>
>since tags from l1 may be missing in l2 and vice versa.
>
>My question is, if there is a better pattern matching or set
>manipulation approach to this problem, since the lists l1 and l2
>might become quite large. Timing for this is the main concern.
>I am looking for a solution which avoids any loop construct.
>
Adalbert,
Here is one approach:
l1 = {{s1, x1}, {s3, x3}, {s4, x4}, {s6, x6}, {s7, x7}};
l2 = {{s2, y2}, {s3, y3}, {s4, y4}, {s5, y5}};
Find common tags
tags = Intersection[
Sequence @@ ((# /. {a_, b_} -> a)& /@ {l1, l2})]
{s3, s4}
Select elements with common tags
sel = Union[Flatten[
Select[#, MemberQ[tags, #[[1]]]&]& /@ {l1, l2}, 1]]
{{s3, x3}, {s3, y3}, {s4, x4}, {s4, y4}}
Merge adjacent elements
(# /. {a_List, b_List} :> Join[a, {b[[2]]}])& /@
Partition[sel, 2]
{{s3, x3, y3}, {s4, x4, y4}}
Bob Hanlon