[Rd] reordering combn(n,p)
rkoenker at uiuc.edu
Thu Feb 14 14:52:23 CET 2008
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
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
More information about the R-devel