[18802] in s-news-athena
RE: [S] Help eliminate a recursive function
daemon@ATHENA.MIT.EDU (Prof Brian D Ripley)
Fri Jul 30 14:09:27 1999
Date: Fri, 30 Jul 1999 18:58:44 +0100 (BST)
From: Prof Brian D Ripley <ripley@stats.ox.ac.uk>
To: "CHASALOW, SCOTT [AG/2165]" <SCOTT.CHASALOW@cereon.com>
Cc: "'Bill.Venables@cmis.csiro.au'" <Bill.Venables@cmis.csiro.au>,
"'moord@email.uc.edu'" <moord@email.uc.edu>,
"'S-NEWS'" <s-news@wubios.wustl.edu>
In-Reply-To: <8D7A3D2453C7D2119CD800A0C9EAF09711FBEA@cereon_033.monsanto.com>
Message-Id: <Pine.GSO.4.05.9907301853080.6305-100000@auk.stats>
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
On Fri, 30 Jul 1999, CHASALOW, SCOTT [AG/2165] wrote:
> the same answers.) Generating (but not doing anything interesting with)
> the 15504 combinations of 1:20 taken 5 at a time took each function
> around 45 seconds on a 300 MHz Pentium running S-PLUS 4.5 under Win NT.
> For much larger problems, I strongly second Bill's comment that this
> "is the sort of territory where dynamically loaded code starts to become
> unavoidable."
As Bill probably has long forgotten, there is C code to do precisely
that in the lqs function in the V&R3 MASS library, as in
/*
Find all subsets of size k in order: this gets a new one each call
*/
void
next_set(Sint * x, int n, int k)
{
int i, j, tmp;
j = k - 1;
tmp = x[j]++;
while (j > 0 && x[j] >= n - (k - 1 - j)) tmp = ++x[--j];
for (i = j + 1; i < k; i++) x[i] = ++tmp;
}
and you will need to look at the code to see how it is initialized
(x is 1:k). (This is often called a Gray code algorithm.)
And although I originally wrote this as a loop in S, doing 100000 subsets
meant that I needed to do it all in C.
--
Brian D. Ripley, ripley@stats.ox.ac.uk
Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/
University of Oxford, Tel: +44 1865 272861 (self)
1 South Parks Road, +44 1865 272860 (secr)
Oxford OX1 3TG, UK Fax: +44 1865 272595
-----------------------------------------------------------------------
This message was distributed by s-news@wubios.wustl.edu. To unsubscribe
send e-mail to s-news-request@wubios.wustl.edu with the BODY of the
message: unsubscribe s-news
