Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Select from list

• To: mathgroup at smc.vnet.net
• Subject: [mg87768] Re: [mg87729] Select from list
• From: Carl Woll <carlw at wolfram.com>
• Date: Wed, 16 Apr 2008 22:30:26 -0400 (EDT)
• References: <200804160904.FAA23961@smc.vnet.net>

Steve Gray wrote:

>I have a list like this:
>
>ptX=
>{{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}}
>
>and I want a list pointing to all the sublists above that contain both
>a 2 and a 3. In this example I would get {1,2,5}. The best solution I
>have, with more generality, is:
>
>va = 2;
>vb = 3;
>za = Map[Cases[#1, va]&, ptX] /. {} -> {0}
>zb = Map[Cases[#1, vb]&, ptX] /. {} -> {0}
>Flatten[Position[za*zb, {va*vb}]]
>
>which gives
>
>{{2}, {2}, {2}, {0}, {2}}
>{{3}, {3}, {0}, {3}, {3}}
>{1, 2, 5}. 
>
>(This doesn't work if va or vb is zero. That's ok.)
>There's probably a better way. Anyone? Thank you.
>
>Steve Gray
>  
>
If you are interested in the fastest possible method for doing this, 
then I would do the following:

First, a helper function:

NonzeroPosition[data_]:=SparseArray[data] /. HoldPattern[SparseArray[__, 
{_,{_,x_},_}]]:>x

Now, I'll use Clip to convert the input into a 1D list which is 1 if the 
a sublist has 2 and 0 if it doesn't, and similarly, for 3.

twos = Unitize @ Total[ Clip[ ptX, {2,2}, {0,0}], {2}];
threes = Unitize @ Total[ Clip[ ptX, {3,3}, {0,0}], {2}];

 From this it is easy to construct a 1D list which is 1 if a sublist has 
both 2 and 3, and 0 otherwise:

twothree = BitAnd[twos, threes];

To convert this 1D list into a list of positions, use NonzeroPosition:

Flatten@NonzeroPosition[twothree];

Putting the above together, we have:

Flatten @ NonzeroPosition @ BitAnd[
    Unitize @ Total[ Clip[ ptX, {2,2}, {0,0}], {2}],
    Unitize @ Total[ Clip[ ptX, {3,3}, {0,0}], {2}]
]

As an example, here is a list of length 10^6, and a timing example:

data = RandomReal[5, {10^6, 5}];

Flatten @ NonzeroPosition @ BitAnd[
    Unitize @ Total[ Clip[ data, {2,2}, {0,0}], {2}],
    Unitize @ Total[ Clip[ data, {3,3}, {0,0}], {2}]
]; //Timing

{0.391,Null}

Carl Woll
Wolfram Research

• References:
  • Select from list
    • From: Steve Gray <stevebg@roadrunner.com>