On ordering of splits and Gray code
(a new trick and its long history)

Jan Klaschka

Institute of Computer Science, Academy of Sciences
Pod Vodárenskou věžı 2, 182 07 Prague 8, Czech Republic
klaschka@cs.cas.cz

In COMPSTAT'98 article [4], Klaschka and Mola dealt with an economical way of calculating, in the tree-based methods, all the $2^{n-1}-1$ values of splitting criterion for the splits based on an $n$-valued categorical variable. We proposed a specific ordering of splits suitable for recalculating one value from another.

The core of the paper was a combinatorial idea: The $(n-1)$-tuples of $0$'s and $1$'s coding the splits can be ordered in a sequence so that any two successive elements differ in exactly one position.

Only later I learned that the same combinatorial idea had already been utilized as early as in the sixties in the all possible subsets regression, see [1], [6].

Moreover, even in the sixties the idea was not quite novel: It was an independent reinvention of so called Gray code, for which Frank Gray took out a patent in 1953 (see [2], [5]).

Gray code seems to possess a high potential of being repeatedly reinvented. By the way, Gray was not the first to invent it: According to [3], it was used by Emile Baudot's telegraph, awarded a gold medal at the Universal Exposition in Paris in 1878.