Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: a tricky List manipulation problem

• To: mathgroup at smc.vnet.net
• Subject: [mg16292] Re: [mg16211] a tricky List manipulation problem
• From: "Wolf, Hartmut" <hwolf at debis.com>
• Date: Sun, 7 Mar 1999 01:05:30 -0500
• Organization: debis Systemhaus
• References: <199903050540.AAA13494@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

Lieber Adalbert,

hanssen at zeiss.de schrieb:
> 
> 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 proposal would be as follows:

Input doesn't need to be sorted, since an intermediate expression will
be sorted. 
It goes as follows:

Test data:

In[1]:= l1= Select[{#, Random[]}& /@ Range[13], #[[2]] <0.8 &]

Out[1]=
{{2,0.163439},{4,0.230896},{5,0.60373},{6,0.258523},{7,0.085896},{8,
    0.0615488},{9,0.175163},{10,0.1535},{11,0.634425},{12,0.119456},{13,
    0.581436}}

In[2]:= l2= Select[{#, Random[]}& /@ Range[13], #[[2]] <0.8 &]
Out[2]=
{{1,0.0410573},{4,0.0762885},{5,0.00372868},{6,0.495109},{8,0.25558},{9,
    0.718798},{11,0.0234612},{12,0.287585},{13,0.555359}}

The helper:

In[3]:= f[{s_, x_}, {t_, y_}] /; s===t := {s, x, y}
In[4]:= f[_,{s_, x_}] := {s, x}

The procedure:

In[5]:= FoldList[f, {}, Union[l1,l2]]
Out[5]=
{{},{1,0.0410573},{2,0.163439},{4,0.0762885},{4,0.0762885,0.230896},{5,
   
0.00372868},{5,0.00372868,0.60373},{6,0.258523},{6,0.258523,0.495109},{7,
   
0.085896},{8,0.0615488},{8,0.0615488,0.25558},{9,0.175163},{9,0.175163,
    0.718798},{10,0.1535},{11,0.0234612},{11,0.0234612,0.634425},{12,
   
0.119456},{12,0.119456,0.287585},{13,0.555359},{13,0.555359,0.581436}}

In[6]:= Select[%, Length[#]==3 &]
Out[6]=
{{4,0.0762885,0.230896},{5,0.00372868,0.60373},{6,0.258523,0.495109},{8,
   
0.0615488,0.25558},{9,0.175163,0.718798},{11,0.0234612,0.634425},{12,
    0.119456,0.287585},{13,0.555359,0.581436}}

I didn't test for performance, but it should do well, please report.

Kind regards, Hartmut

Hartmut Wolf, debis Systemhaus, Darmstadt, Germany
=============[mailto:hwolf at debis.com]=============

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