9
$\begingroup$

I am wondering if there is a natural Mathematica way to generalize those functions. To be specific, All three functions AllTrue, AnyTrue and NoneTrue return a Boolean value when a list of length L contains certain number of elements satisfying a predicate.

For example, AllTrue returns true when the number of elements satisfying the predicate is L while NoneTrue returns true when the number is 0. On the contrary, AnyTrue returns true when the number is at least 1.

I am considering the generalization SomeTrue[ list, pred, n] that it returns true when the number is at least n.

Another generalization might be SomeTrue[ list, pred, {n}] that it returns true when the number is exactly n.

One natural way I can think of is just using Count function to calculate the number and compare the criterion but it does not allow the early exit(i.e., every element should be checked even for the case where the result is determined in the early stage).

For people like me migrating from procedural language, the algorithm might be obvious using For loop with counters and early return statements. It would be nice if you can show some examples with truly Mathematica way to attack such problems.

$\endgroup$
  • $\begingroup$ Note: kguler mentioned BooleanCountingFunction. Unfortunately it doesn't appear applicable here as I cannot think of a way to give it early-exit behavior, so one might as well use Count. $\endgroup$ – Mr.Wizard Jan 14 '15 at 11:12
  • 1
    $\begingroup$ I'd go with While myself. One could use Scan and THrow/Catch, say. But really I don't see an early exit method that does not, at heart, emulate procedural code. $\endgroup$ – Daniel Lichtblau Jan 15 '15 at 0:36
10
$\begingroup$

Select is fairly close to this already, notably including early exit behavior, so perhaps:

someTrue[list_, pred_, {m_} | n_] :=
  n + m == Length @ Select[list, pred, 1 n + m]

Test:

someTrue[Range@10, PrimeQ, 3]
someTrue[Range@10, PrimeQ, 5]
someTrue[Range@10, PrimeQ, {4}]
someTrue[Range@10, PrimeQ, {2}]
True

False

True

False

The code above is me trying to be clever with vanishing patterns. The longer but more legible form:

someTrue[list_, pred_, n_]   := n == Length @ Select[list, pred, n]
someTrue[list_, pred_, {n_}] := n == Length @ Select[list, pred, n + 1]
$\endgroup$
  • $\begingroup$ Thank you. I did not know about the variants of Select. Also thanks for the introduction of vanishing patterns which I have not encountered yet :). $\endgroup$ – Sungmin Jan 14 '15 at 12:59
  • $\begingroup$ I see; vanishing patterns necessitates the inclusion of 1 in 1 n + m. Also, clever use of Length@Select[..., n + 1] to test for exactly n length. +1 $\endgroup$ – rcollyer Jan 22 '15 at 19:29
  • $\begingroup$ @rcollyer Yes, and thank you. $\endgroup$ – Mr.Wizard Jan 22 '15 at 19:46
6
$\begingroup$

Here's a way to implement this without Select, but with VectorQ. If you don't want to duplicate memory, then Select could be dangerous.

My idea was to count the number of times pred was true and exit once it hit's the specified threshold.

SomeTrue[list_, pred_, n_Integer] := Module[{i = 0},
  !VectorQ[list, (If[pred[#], i++]; i < n)&]
]

SomeTrue[list_, pred_, {n_Integer}] := Module[{i = 0},
  VectorQ[list, (If[pred[#], i++]; i < n+1)&] && i == n
]
$\endgroup$
  • 1
    $\begingroup$ +1 for the idea but it would be preferred to use Module instead of Block. $\endgroup$ – Mr.Wizard Jan 15 '15 at 17:04
  • $\begingroup$ On unpacked lists Select has a significant advantage being about five times as fast as this. However VectorQ does not unpack therefore this saves memory there as well and also avoids the time taken to unpack. $\endgroup$ – Mr.Wizard Jan 15 '15 at 17:22
  • $\begingroup$ Could you elaborate the statement "If you don't want to duplicate memory"? $\endgroup$ – Sungmin Jan 15 '15 at 19:03
  • 1
    $\begingroup$ @Sungmin (1) Select gathers a new list of results that pass the test function, and this new list takes memory. Further Select unpacks packed arrays therefore if your list is a large packed array it will first be expanded to several times its original size; VectorQ does not unpack. See: (8652). $\endgroup$ – Mr.Wizard Jan 15 '15 at 19:11
  • 3
    $\begingroup$ @Sungmin (2) Module is preferred because it is the correct tool to create a localized Symbol for e.g. a counter. Block modifies the value of the global Symbol (i). This means that if for example you define ex = {3, h, i, j, k}; and then do SomeTrue[ex, NumericQ, 2] you get True even though there is only one numeric element in ex. This happens because inside the Block i has a numeric value. This collision is avoided by using Module. I used to misuse Block quite often and I can tell you from experience it leads to nasty bugs. $\endgroup$ – Mr.Wizard Jan 15 '15 at 19:13
0
$\begingroup$
If[Count[Boole[list], 1] == n, True, False]

where n is the number of Trues you require

$\endgroup$
  • 2
    $\begingroup$ No early exit here. In fact the question specifically mentions Count as a suboptimal solution. $\endgroup$ – Oleksandr R. Jan 14 '15 at 10:44
  • $\begingroup$ Also you don't need If -- Count[Boole[list], 1] == n will do. $\endgroup$ – Mr.Wizard Jan 14 '15 at 11:08
  • $\begingroup$ Here's an Experiment you might like to try: (* This generates a list of 1 million random Boolean equations *) blist = Table[ RandomChoice[{Equal, Unequal, Greater, Less}][ RandomInteger[{1, 100}], RandomInteger[{1, 100}]], {i, 1, 10^6}]; (* This checks to see if number of True results is between 300,000 and 350,000 *) 300000 < Count[Boole[blist], 1] < 350000 Of course you may change these parameters and see if it is fast enough. $\endgroup$ – david.F Jan 14 '15 at 22:29
  • $\begingroup$ If the test function is fast and you are checking most of the elements anyway Count is fine. However sometimes the test function is slow and you don't want to run it on all of the elements. For example consider mers = 2^Range[5000] - 1; and the performance of someTrue[mers, PrimeQ, 7], then compare your method. $\endgroup$ – Mr.Wizard Jan 14 '15 at 23:50
  • $\begingroup$ Tried this method for Mersene Primes up to 2^5000 -1,Around 10 secs it took. mersprlist = Table[PrimeQ[2^i - 1], {i, 1, 5000}]; Count[Boole[mersprlist], 1] $\endgroup$ – david.F Jan 15 '15 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.