Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: a tricky List manipulation problem

• To: mathgroup at smc.vnet.net
• Subject: [mg16337] Re: [mg16211] a tricky List manipulation problem
• From: Jurgen Tischer <jtischer at col2.telecom.com.co>
• Date: Sun, 7 Mar 1999 01:05:53 -0500
• Organization: Universidad del Valle
• References: <199903050540.AAA13494@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

Adalbert,
I can't see why you wouldn't allow loop constructs, in any case there
will be internal loops, and using loops is the only way I see how you
can use the property that the lists are already sorted. Anyway here are
three functions which will do what you want, number two is an
implementation of what you called "down the ladder". It's the fastest
one.

f1[li1_, li2_] := 
  Module[{ll = 
     Flatten[Cases[Partition[Sort[Join[li1, li2]], 2, 
        1], {{a_, b_}, {a_, c_}}], 1], l1, l2}, 
   l1 = Intersection[ll, li1]; l2 = Intersection[ll, li2]; 
    Transpose[Append[Transpose[l1], Transpose[l2][[2]]]]]

f2[li1_, li2_] := 
  Module[{l1 = 
     Intersection[Transpose[li1][[1]], 
      Transpose[li2][[1]]], n1 = 1, n2 = 1, ll = {}}, 
   ((While[li1[[n1,1]] < #1, n1++]; 
         While[li2[[n2,1]] < #1, n2++]; 
         ll = {ll, li1[[n1]], li2[[n2,2]]}; ) & ) /@ l1; 
    Partition[Flatten[ll], 3]]

f3[li1_, li2_] := 
  Module[{l1 = 
     Intersection[Transpose[li1][[1]], 
      Transpose[li2][[1]]], f1}, 
   ((f1[#1] = True) & ) /@ l1; 
    Transpose[Append[Transpose[Select[li1, 
        f1[#1[[1]]] & ]], 
      Transpose[Select[li2, f1[#1[[1]]] & ]][[2]]]]]


Jurgen

hanssen at zeiss.de wrote:
> 
> Hi, MathGroup
> 
> 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.
> 
> Best regards
> 
> Dipl.-Math. Adalbert Hanszen

• References:
  • a tricky List manipulation problem
    • From: hanssen@zeiss.de