"logo.gif"  
Main
Read Online
Download PDF
Additional resources
Revision history
Known typos/bugs
Report a bug
License terms
About the author
"node596_1.gif" "node596_2.gif" "node596_3.gif"

6.5.5.3    Positions of member elements - developing the memberPositions function

It looks like we have reached the full stop: Position is a built-in operation specially designed for finding many positions at once, and we have supplied a large alternative pattern which speeds-up the pattern-matching. However, we can do better. Let us think if we can write our own function that will find all the positions of the member elements. To develop such a function, let us start once again with a simple member list and test list

"node596_4.gif"

"node596_5.gif"

"node596_6.gif"

"node596_7.gif"

As a first step, let us find an ordering permutation which is needed to sort <testlst>, using the standard Ordering command:

"node596_8.gif"

"node596_9.gif"

The numbers here indicate a sequence of positions, so that if we extract the elements at these positions in this order, we get a sorted list:

"node596_10.gif"

"node596_11.gif"

Here, I used the capability of Part to extract many elements at once.

By using a well-known for us by now combination of Split, Length, Transpose and Map  (see section 3.10.3.4), we can obtain a list of unique (distinct) elements plus a list of their frequencies (which are given just by lengths of the sublists of same elements which Split produces):

"node596_12.gif"

"node596_13.gif"

Now we would like to know, to which intervals of positions in the original sorted list correspond the sublists of identical elements produced by Split. Since the list of frequencies is at the same time the list of lengths of these sublists, the general formulation of our sub-problem is to obtain a list of position intervals given a  partition of the length of the main list into lengths of sublists. For example, for a list Range[10] and length partitioning {1,3,4,2}, we should get the following position list : {{1,1},{2,4},{5,8},{9,10}}.  The way to solve this problem is to construct partial sums of the length list by using the FoldList. This will give the starting points of the intervals when we remove the last element, and  the endpoints when we subtract 1 from this list and remove the first element. Then we need to Transpose the resulting two lists. So, here is the code:

"node596_14.gif"

"node596_15.gif"

By using a pure function like this, we can avoid an introduction of an auxiliary variable to hold the result of FoldList operation. This is a generally useful trick.

What we would like to do now is to create a set of rules, relating each distinct element in a list to an interval of positions where this element (identical copies of it) is present in a sorted list. This is done in a standard way using Thread (see section 5.3.1.5).

"node596_16.gif"

"node596_17.gif"

The next and absolutely crucial step is to use Dispatch, to create a hashed version of our set of rules:

"node596_18.gif"

"node596_19.gif"

Now we can find members of the first list which are also members of the second list, as before, by using Intersection:

"node596_20.gif"

"node596_21.gif"

The next step is to find intervals of positions in the sorted list which correspond to these elements. We use our Dispatched rules for that:

"node596_22.gif"

"node596_23.gif"

Now we will use Range with the Map[Apply,..] (@@@, see section 5.2.7.5), to generate all the positions from position intervals:

"node596_24.gif"

"node596_25.gif"

We will also Flatten this list, since we no longer need the internal braces:

"node596_26.gif"

"node596_27.gif"

To get a corresponding list of positions of these elements in the original unsorted list, we recall that we have an access to an ordering permutation. All we have to do is just to extract from this permutation the elements (positions in an unsorted list) which are at the positions we have just found. This is perhaps the most logically non-trivial step in the whole procedure and may take a bit to digest. Anyway, here is the result:

"node596_28.gif"

"node596_29.gif"

The final step is to Sort these positions:

"node596_30.gif"

"node596_31.gif"

Let me display both lists again so that we can see that these positions indeed are the positions of he common members of the two lists, in the first list:

"node596_32.gif"

"node596_33.gif"

"node596_34.gif"

"node596_35.gif"

This was a terribly long discussion (it actually took me several times less time to write this function than to describe it), but let us now condense all the steps into a single function:

"node596_36.gif"

Let us check again that it gives the right thing:

"node596_37.gif"

"node596_38.gif"

"node596_39.gif"

"node596_40.gif"

"node596_41.gif"

"node596_42.gif"

The function we have just developed represents some value by itself, but now we will use it in our problem.

"node596_43.gif" "node596_44.gif" "node596_45.gif"

Created by Wolfram Mathematica 6.0  (05 February 2009) Valid XHTML 1.1!