Function like Cases/Select which also returns complement

Question

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.)

Answer 1

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}} *)

Answer 2

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}}

Answer 3

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}