Re: Count pattern
- To: mathgroup at smc.vnet.net
- Subject: [mg41305] Re: Count pattern
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Wed, 14 May 2003 08:10:29 -0400 (EDT)
- Organization: University of Washington
- References: <b9qabm$htm$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Soren,
You will undoubtedly get many responses, as the newsgroup enjoys turning
these simple requests into a speed competition. In that vein, I will provide
a solution which is O((n+m)Log[n+m]), where n and m are the lengths of s and
t. The most obvious solutions (to me, at least) are all O(n m), so the
solution I provide ought to be one of the fastest for large n and m. If
speed is not important, then you may be better off with one of the slower,
but probably easier to understand approaches.
At any rate, my idea was to mark one of the lists somehow, then combine the
lists and sort. Once sorted, the positions of the marked list ought to tell
you how many elements were greater. Assuming you were working with real
data, one possibility is to mark the list by adding a the imaginary number
I, since Mathematica automatically sorts based on the real part of complex
quantities. Here is the function definition:
soren[t_,s_]:=
Length[s]-
Flatten[Position[Sort[Join[t,s+I]],_Integer]]+
Range[Length[t]]
and your example:
In[21]:=
soren[t,s]
Out[21]=
{33, 30, 28, 27, 26, 25, 24, 23, 21, 20, 18, 17, 15, 13, 12, 10, 6}
The only thing that needs further mention is the pattern _Integer in the
Position statement. If your data is not strictly integer, you will need to
change this pattern. If your data is strictly positive, then _?Positive is a
possibility. Otherwise, you may need to change this pattern to something
like _?(Element[#,Reals]&). In any case, the pattern should be designed to
reject complex quantities and accept real quantities.
Carl Woll
Physics Dept
U of Washington
"Søren Merser" <merser at image.dk> wrote in message
news:b9qabm$htm$1 at smc.vnet.net...
>
> hi there
>
> i need a litle help on a problem that has puzzeled me for some time
>
> i want to count the number of elements in s with value greater or equal
> to each element in t
>
> t = {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 17, 27, 28, 30, 36, 50}
>
> s = {1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 8, 10, 12, 12, 14, 17, 20, 27,
> 27, 28, 30, 30, 36, 38, 40, 45, 50, 50, 50, 63, 132, 132}
>
> the result should be: {33, 30, 28, 27, 26, 25, 24, 23, 21, 20, 18, 17,
> 15, 13, 12, 10, 6}
>
>
>
> kind regards soren
>
>