[R] all possible samples

[(Ted Harding)]

On 17-Sep-03 lamack lamack wrote:
> Dear all, there is an R function that return all possible samples of
> size n, 
> with replacement,  from a vector of length N ?

Without delving into R to see if such a thing exists already, I can
suggest the following (based on an algorithm to be found in Nijenhuis
and Wilf, "Combinatorial Algortithms", Academic Press 1978). I once
implemented it in octave and it worked well. I'll use their notation
rather than yours so that I don't confuse my fingers ...

To select all subsets of size k out of n (in "lexicographic order"):

The n-set is {1,2,3,...,n}.
A selected subset is {a[1],a[2],...,a[k]}.

Repeatedly apply the following algorithm for "next subset":

(A) If first time (first subset): m<-0; h<-k; go to (D)
(B) If not first time: if( m>=n-h ) go to (C); else h<-0;
(C) h<-(h+1); m<-a[k+1-h];
(D) for(j in (1:h)) {a[k+j-h]<-(m+j)};
    if( a[1]==(n-k+1)) final_exit (all done);
    else nonfinal_exit (some left);

For 3 out of 5 this gives {1,2,3},(1,2,4},{1,2,5},{1,3,4},{1,3,5},
{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}.

Best wishes,
Ted.


--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at nessie.mcc.ac.uk>
Fax-to-email: +44 (0)870 167 1972
Date: 17-Sep-03                                       Time: 20:21:32
------------------------------ XFMail ------------------------------