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.

Improve this question
$\endgroup$
2
  • $\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, 2015 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, 2015 at 0:36

3 Answers 3

Reset to default
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]
Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 at 19:29
  • $\begingroup$ @rcollyer Yes, and thank you. $\endgroup$
    – Mr.Wizard
    Jan 22, 2015 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
]
Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ +1 for the idea but it would be preferred to use Module instead of Block. $\endgroup$
    – Mr.Wizard
    Jan 15, 2015 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, 2015 at 17:22
  • $\begingroup$ Could you elaborate the statement "If you don't want to duplicate memory"? $\endgroup$
    – Sungmin
    Jan 15, 2015 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, 2015 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, 2015 at 19:13
0
$\begingroup$ 
If[Count[Boole[list], 1] == n, True, False]

where n is the number of Trues you require

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ No early exit here. In fact the question specifically mentions Count as a suboptimal solution. $\endgroup$
    – Oleksandr R.
    Jan 14, 2015 at 10:44
  • $\begingroup$ Also you don't need If -- Count[Boole[list], 1] == n will do. $\endgroup$
    – Mr.Wizard
    Jan 14, 2015 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, 2015 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, 2015 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, 2015 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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