How does a decision tree split on a categorical variable? [duplicate]

Some implementations of decision trees (eg cran/tree) can split on categorical variables where the split separates the variable into 2 groups:

> library("tree")

> tree(Survived ~ Class, data=df, weights=Freq, minsize=10)
node), split, n, deviance, yval, (yprob)
* denotes terminal node

1) root 2201 2769 No ( 0.6770 0.3230 )
2) Class: 3rd,Crew 1591 1772 No ( 0.7549 0.2451 ) *
3) Class: 1st,2nd 610  844 Yes ( 0.4738 0.5262 ) *

For a numerical variable, splits are calculated by trying all possible splits between the minimum and maximum value of the variable.

How are the splits enumerated for a categorical variable? Do you have to try all combinations of values? (this would seem to be computationally crazy) Or is there a heuristic you use to limit the number of combinations tried?

• To my understanding, Weka's J48 is supposed to be an implementation of C4.5, which is contrasted from CART in several ways, as described in Top 10 algorithms in data mining (which has Quinlan as a coauthor, so one would guess that's accurate about the distinctions) Jun 6 '17 at 0:02
• thanks for the link @Glen_b, in the article they say "An attribute A with discrete values has by default one outcome for each value, but an option allows the values to be grouped into two or more subsets with one outcome for each subset." But they don't say how this grouping is achieved -- this is what I'm asking in my question. Jun 6 '17 at 0:11
• BTW i've removed CART from the title if this makes things clearer Jun 6 '17 at 0:15
• This image shows that you can get more than a binary split (see the region variable), (or equivalently, p22 of this, see the outlook variable -- also see p7 here). If you question is "how do I make Weka do this?" it will be off topic here (see under Programming). Jun 6 '17 at 0:19
• This document (again, Quinlan is a coauthor): Decision Tree Discovery under "Candidate tests" (p3) gives a brief discussion of how C4.5 deals with categorical variables. If j48 implements C4.5 correctly (you can always check the code), presumably it works like this. Jun 6 '17 at 0:35