Function like Cases/Select which also returns complement

I'm looking for a function similar to Cases or Select, but that also returns the complement of the resulting list.

In other words, given some pattern, I want to split a list into two pieces: one piece whose elements match the pattern, and another piece whose elements do not match the pattern. I'd also be interested in a corresponding function that works with Select-style input rather than Cases-style input.

It's obvious how to do this in two function calls, but I only want to run through the list once. (In the case of a long list, I don't want the combined operation to take the time.)

• Welcome to Mathematica.SE! I suggest that: 1) You take the introductory Tour now! 2) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! 3) As you receive help, try to give it too, by answering questions in your area of expertise. Feb 8, 2015 at 0:33
• user, I encourage everyone to wait 24 hours before Accepting an answer to let people around the world have a chance to respond. In this case I think my answer is more complete than those provided before it and I hope you will consider it. Feb 8, 2015 at 5:26
• @Mr.Wizard I appreciate the advice, but I wouldn't consider your answer more complete without at least mentioning the built in function GatherBy. That aside, the other points you brought up were helpful. Feb 8, 2015 at 19:53
• Please see my updated answer. Feb 8, 2015 at 20:04

3 Answers

Update: If you have Version 10, you can use GroupBy:

Values@GroupBy[OddQ][Range[10]]
(* {{1, 3, 5, 7, 9}, {2, 4, 6, 8, 10}} *)


Values@GroupBy[Range[10],OddQ] gives the same result.

Perhaps GatherBy with a boolean second argument, e.g.,

GatherBy[Range[10], OddQ]
(* {{1, 3, 5, 7, 9}, {2, 4, 6, 8, 10}} *)


If your test can described as a binary pass/fail and it will only be applied at the first level of a List it is likely most efficient to use GroupBy or GatherBy. GroupBy makes it easy to order the result e.g. always pass (true) first:

GroupBy[Range@20, PrimeQ] /@ {True, False}

{{2, 3, 5, 7, 11, 13, 17, 19}, {1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}}


If you are using an earlier version of Mathematica you will have to order the result of GatherBy:

SortBy[GatherBy[Range@20, PrimeQ], 1 - Boole @ PrimeQ @ First @ # &]

{{2, 3, 5, 7, 11, 13, 17, 19}, {1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}}


However Cases does more than this:

• it works on arbitrary expressions
• it works with patterns
• it performs replacements
• it takes a levelspec and the Heads option

The earlier answers did not address these points, therefore I shall, with:

separate[expr_, (L_ -> R_) | (L_ :> R_) | L_, arg___] :=
Quiet @ Replace[L | _?(Sow@#; &) :> R, _[x_] :> x] //
Reap[Cases[expr, #, arg], _, Sequence @@ #2 &] &

• The syntax is the same as Cases including levelspec and the Heads option, as these are passed directly to Cases itself.

• _?(Sow@#; &) serves as a fall-through when the given pattern does not match, therefore only non-matches are sown.

Examples:

separate[Range@10, x_?OddQ :> x/2]

{{1/2, 3/2, 5/2, 7/2, 9/2}, {2, 4, 6, 8, 10}}

separate[
{{foo, Pi}, -9.3, {False, 1.1}, 1, f[5, 7], True, 3/4},
_[x_, _] :> x
]

{{foo, False, 5, 3}, {-9.3, 1, True}}    (* 3 is split from Rational[3, 4] *)

separate[
{{foo, Pi}, -9.3, {False, 1.1}, 1, f[5, 7], True, 3/4},
_Symbol, {2}, Heads -> True
]

{{List, foo, π, List, False, f}, {1.1, 5, 7}}


One straightforward way is to select the items you want and then take the complement of the set:

set = Select[Range[20], Mod[#, 3] == 1 &];
notSet = Complement[Range[20], set];


Speed-wise there is not much difference between this and GatherBy:

Timing[n = 1000000; full = Range[n];
set = Select[full, Mod[#, 3] == 1 &];
notSet = Complement[full, set];]
{0.803090, Null}

Timing[n = 1000000; full = Range[n];
GatherBy[full, Mod[#, 3] == 1 &];]
{0.982641, Null}