Sampling Without Replacement from Multisets

by
Paraskevas V. Lekeas 
National Technical University of Athens
Algorithms and Logic Lab
plekeas@mail.ntua.gr
Thessalias 4, 15772, Zografou,
Greece

12 July 2004

Sampling without replacement from multisets

The following are for sampling a list without replacement. When we say a list, in fact we mean a multiset. This means that this list may have multiple elements of the same kind, which have to be treated as different when sampling.

Here we define a function called rnd which gets as input the list we want to sample, computes its Length and picks a random integer between 1 and Length.

rnd[ll_] := Random[Integer, {1, Length[ll]}]

Here we define another function, takelement,which gets as input the list we want to sample and extracts the ith element of the list where i equals to the random number drawn previously by rnd.

takelement[ll_] := t = Take[l, {aa = rnd[l], aa}]

Here we define an empty list where we should put the sampled elements.

emptylist := {}

Here we define a function that drops the sampled element from list l (sampling without replacement).

dropelement[k_] := l = Drop[l, {aa, aa}]

Here we define a function which represents the final sample. By calling this function we just append in each iteration the sampled element.

sample := Flatten[AppendTo[emptylist, t]]

Here all the functions are placed together as a procedure called gyros.

gyros[n_] := (takelement[l_]; dropelement[l_]; sample)

At last we Nest procedure gyros by giving as input the list and the sample size we want to draw. Be careful that we have to name our sample only with the letter l, and of course we have to have define that list first!

Instructions on how to use

Load in memory (Shift+Enter) all the previous functions.
Load the list from where you will get the sample. Name that list with letter l.
Decide the size of your sample. 
Be careful, when you want to draw another sample you have to reevaluate function emptylist in order to begin with an empty sample list, and also reevaluate the starting list in order to draw samples from the same starting list.

Example

Here is a list (multiset) of Length 99:

l:={10.5000000000000004`,10.3600000000000003`,12.5700000000000011`,24.950000000000001`,12.5700000000000011`,16.0700000000000002`,13.2699999999999995`,17.4699999999999988`,15.3699999999999992`,11.8900000000000005`,10.4700000000000015`,31.4699999999999979`,19.9499999999999992`,13.2699999999999995`,29.950000000000001`,16.9499999999999984`,16.0700000000000002`,11.8900000000000005`,13.9700000000000002`,13.2699999999999995`,13.2699999999999995`,10.3600000000000003`,9.56000000000000049`,12.5700000000000011`,17.9499999999999992`,13.9700000000000002`,17.4699999999999988`,11.8699999999999983`,19.`,13.2699999999999995`,9.56000000000000049`,30.6700000000000017`,12.9499999999999992`,13.9700000000000002`,29.950000000000001`,13.2699999999999995`,11.8900000000000005`,11.8900000000000005`,32.0000000000000017`,10.3600000000000003`,32.0000000000000017`,12.5700000000000011`,24.950000000000001`,34.950000000000001`,32.0000000000000017`,72.0000000000000017`,13.9500000000000001`,11.8699999999999983`,19.25`,44.0000000000000035`,29.`,16.0700000000000002`,21.0000000000000008`,19.9499999999999992`,14.9499999999999992`,37.799999999999998`,31.0000000000000008`,22.9499999999999992`,18.5`,24.950000000000001`,10.3600000000000003`,4.95000000000000017`,16.9499999999999984`,21.9499999999999984`,25.6400000000000005`,11.8699999999999983`,12.5700000000000011`,52.0000000000000017`,12.9499999999999992`,20.9499999999999975`,10.4700000000000015`,12.9499999999999992`,11.1999999999999988`,44.950000000000001`,14.5`,10.6999999999999984`,23.5499999999999998`,14.9499999999999992`,29.950000000000001`,21.3600000000000012`,27.5`,5.95000000000000017`,20.`,18.75`,26.4999999999999991`,11.1899999999999999`,14.5`,35.`,11.1699999999999999`,13.9999999999999991`,18.6000000000000014`,42.4600000000000044`,94.9500000000000099`,20.9499999999999975`,79.950000000000001`,12.9499999999999992`,55.`,7.95000000000000017`,27.1999999999999975`}

Here we ensure that we start from the empty list:

emptylist := {}

Here we draw without replacement a sample s1 of size 10 from list l:

s1 = Nest[gyros[#]&, l, 10]

Here we verify that the size of the remaining list plus the size of s1 equals to the size of the list before the sampling:

Length[l] + Length[s1]

Since l has been changed (we erased from it all the drawn elements) If we would like to draw another sample from l, we have to reevaluate it, reevaluate the emptylist and go on.