[Rd] reordering combn(n,p)

[roger koenker]

I found the following slightly surprising and thought that it might
(eventually) be useful to someone to document it:

Problem:  I wanted to reorder the columns of the matrix produced
by combn(n,p) so that adjacent columns only differed by one  element.

I assumed that this was a problem known to the Assyrians and
resisted the temptation to write to r-help, and through assiduous
googling finally discovered that this was still a topic of current
research in computer science.

Solution:   Limin Xiang and Kazuo Ushijima (2001) "On O(1) Time  
Algorithms for
Combinatorial Generation," Computer Journal, 44(4), 292-302.
provides a nice algorithm (in Pascal) which I then translated into
ratfor and plan to incorporate eventually into quantreg.  It manages
to do n=500 p = 3 in about 3 secs on my old G5.  It probably
isn't of interest to do problems too much bigger than this since
we are already at 20 x 10^6 columns.

url:    www.econ.uiuc.edu/~roger            Roger Koenker
email    rkoenker at uiuc.edu            Department of Economics
vox:     217-333-4558                University of Illinois
fax:       217-244-6678                Champaign, IL 61820