1 //******************************************************************************
2 //
3 // File: RandomSample.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.RandomSample
6 //
7 // This Java source file is copyright (C) 2010 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.util;
41
42 import java.util.Iterator;
43 import java.util.NoSuchElementException;
44
45 /**
46 * Class RandomSample provides objects that generate random samples from
47 * discrete sets.
48 *
49 * @author Alan Kaminsky
50 * @version 15-Feb-2010
51 */
52 public class RandomSample {
53
54 // Prevent construction.
55 private RandomSample() {
56 }
57
58 // Exported operations.
59 /**
60 * Create an iterator that generates a random sample of <code>int</code>s
61 * without replacement. The set to be sampled consists of the integers from
62 * 0 through <I>N</I>−1 inclusive. The sample consists of <I>n</I>
63 * items. Each item in the set is equally likely to occur in the sample. The
64 * iterator returns the items in the sample in ascending order. The iterator
65 * uses the given <code>prng</code> to sample items at random. For each item
66 * returned, the iterator consumes one random number from the <code>prng</code>.
67 * <P>
68 * As a special case, if <I>n</I> ≥ <I>N</I>, then the iterator returns
69 * all items in the set in ascending order, and the iterator does not use
70 * the <code>prng</code>.
71 * <P>
72 * The iterator uses the algorithm in A. Bissell, Ordered random selection
73 * without replacement, <I>Applied Statistics,</I> 35(1):73-75, 1986.
74 *
75 * @param prng Pseudorandom number generator.
76 * @param n Number of items in the sample.
77 * @param N Number of items in the set.
78 * @return Iterator over the sample.
79 * @exception IllegalArgumentException (unchecked exception) Thrown if
80 * <I>n</I> < 0 or <I>N</I> < 0.
81 */
82 public static Iterator<Integer> withoutReplacement(final Random prng,
83 final int n,
84 final int N) {
85 if (n < 0) {
86 throw new IllegalArgumentException("RandomSample.withoutReplacement(): n < 0 illegal");
87 } else if (N < 0) {
88 throw new IllegalArgumentException("RandomSample.withoutReplacement(): N < 0 illegal");
89 } else if (n < N) {
90 return new Iterator<Integer>() {
91 private int i = 0;
92 private int M = N;
93 private int r = N - n;
94
95 public boolean hasNext() {
96 return i < n;
97 }
98
99 public Integer next() {
100 if (i >= n) {
101 throw new NoSuchElementException();
102 }
103 ++i;
104 double x = prng.nextDouble();
105 double p = 1.0;
106 for (;;) {
107 p = p * r / M;
108 if (p <= x) {
109 int result = N - M;
110 --M;
111 return result;
112 } else {
113 --M;
114 --r;
115 }
116 }
117 }
118
119 public void remove() {
120 throw new UnsupportedOperationException();
121 }
122 };
123 } else {
124 return new Iterator<Integer>() {
125 private int i = 0;
126
127 public boolean hasNext() {
128 return i < N;
129 }
130
131 public Integer next() {
132 if (i >= N) {
133 throw new NoSuchElementException();
134 }
135 return i++;
136 }
137
138 public void remove() {
139 throw new UnsupportedOperationException();
140 }
141 };
142 }
143 }
144
145 /**
146 * Generate a random sample of <code>int</code>s without replacement. The set to
147 * be sampled consists of the integers from 0 through <I>N</I>−1
148 * inclusive. The sample consists of <I>n</I> items. Each item in the set is
149 * equally likely to occur in the sample. The items in the sample are stored
150 * in ascending order in the given <code>buf</code> starting at index 0. The
151 * iterator uses the given <code>prng</code> to sample items at random. For each
152 * item sampled, the iterator consumes one random number from the
153 * <code>prng</code>.
154 * <P>
155 * As a special case, if <I>n</I> ≥ <I>N</I>, then all items in the set
156 * are stored in ascending order in the given <code>buf</code> starting at index
157 * 0, and the iterator does not use the <code>prng</code>.
158 * <P>
159 * This method uses the algorithm in A. Bissell, Ordered random selection
160 * without replacement, <I>Applied Statistics,</I> 35(1):73-75, 1986.
161 *
162 * @param prng Pseudorandom number generator.
163 * @param n Number of items in the sample.
164 * @param N Number of items in the set.
165 * @param buf Array in which to store the sampled items.
166 * @return Number of sampled items actually stored in <code>buf</code>.
167 * @exception IllegalArgumentException (unchecked exception) Thrown if
168 * <I>n</I> < 0 or <I>N</I> < 0.
169 * @exception NullPointerException (unchecked exception) Thrown if
170 * <code>buf</code> is null.
171 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if
172 * <code>buf.length</code> < <code>n</code>.
173 */
174 public static int withoutReplacement(Random prng,
175 int n,
176 int N,
177 int[] buf) {
178 if (n < 0) {
179 throw new IllegalArgumentException("RandomSample.withoutReplacement(): n < 0 illegal");
180 } else if (N < 0) {
181 throw new IllegalArgumentException("RandomSample.withoutReplacement(): N < 0 illegal");
182 } else if (n < N) {
183 int M = N;
184 int r = N - n;
185 for (int i = 0; i < n; ++i) {
186 double x = prng.nextDouble();
187 double p = 1.0;
188 for (;;) {
189 p = p * r / M;
190 if (p <= x) {
191 buf[i] = N - M;
192 --M;
193 break;
194 } else {
195 --M;
196 --r;
197 }
198 }
199 }
200 return n;
201 } else {
202 for (int i = 0; i < N; ++i) {
203 buf[i] = i;
204 }
205 return N;
206 }
207 }
208
209 /**
210 * Create an iterator that generates a random sample of <code>long</code>s
211 * without replacement. The set to be sampled consists of the integers from
212 * 0 through <I>N</I>−1 inclusive. The sample consists of <I>n</I>
213 * items. Each item in the set is equally likely to occur in the sample. The
214 * iterator returns the items in the sample in ascending order. The iterator
215 * uses the given <code>prng</code> to sample items at random. For each item
216 * returned, the iterator consumes one random number from the <code>prng</code>.
217 * <P>
218 * As a special case, if <I>n</I> ≥ <I>N</I>, then the iterator returns
219 * all items in the set in ascending order, and the iterator does not use
220 * the <code>prng</code>.
221 * <P>
222 * The iterator uses the algorithm in A. Bissell, Ordered random selection
223 * without replacement, <I>Applied Statistics,</I> 35(1):73-75, 1986.
224 *
225 * @param prng Pseudorandom number generator.
226 * @param n Number of items in the sample.
227 * @param N Number of items in the set.
228 * @return Iterator over the sample.
229 * @exception IllegalArgumentException (unchecked exception) Thrown if
230 * <I>n</I> < 0 or <I>N</I> < 0.
231 */
232 public static Iterator<Long> withoutReplacement(final Random prng,
233 final int n,
234 final long N) {
235 if (n < 0) {
236 throw new IllegalArgumentException("RandomSample.withoutReplacement(): n < 0 illegal");
237 } else if (N < 0L) {
238 throw new IllegalArgumentException("RandomSample.withoutReplacement(): N < 0 illegal");
239 } else if (n < N) {
240 return new Iterator<Long>() {
241 private int i = 0;
242 private long M = N;
243 private long r = N - n;
244
245 public boolean hasNext() {
246 return i < n;
247 }
248
249 public Long next() {
250 if (i >= n) {
251 throw new NoSuchElementException();
252 }
253 ++i;
254 double x = prng.nextDouble();
255 double p = 1.0;
256 for (;;) {
257 p = p * r / M;
258 if (p <= x) {
259 long result = N - M;
260 --M;
261 return result;
262 } else {
263 --M;
264 --r;
265 }
266 }
267 }
268
269 public void remove() {
270 throw new UnsupportedOperationException();
271 }
272 };
273 } else {
274 return new Iterator<Long>() {
275 private long i = 0L;
276
277 public boolean hasNext() {
278 return i < N;
279 }
280
281 public Long next() {
282 if (i >= N) {
283 throw new NoSuchElementException();
284 }
285 return i++;
286 }
287
288 public void remove() {
289 throw new UnsupportedOperationException();
290 }
291 };
292 }
293 }
294
295 /**
296 * Generate a random sample of <code>long</code>s without replacement. The set
297 * to be sampled consists of the integers from 0 through <I>N</I>−1
298 * inclusive. The sample consists of <I>n</I> items. Each item in the set is
299 * equally likely to occur in the sample. The items in the sample are stored
300 * in ascending order in the given <code>buf</code> starting at index 0. The
301 * iterator uses the given <code>prng</code> to sample items at random. For each
302 * item sampled, the iterator consumes one random number from the
303 * <code>prng</code>.
304 * <P>
305 * As a special case, if <I>n</I> ≥ <I>N</I>, then all items in the set
306 * are stored in ascending order in the given <code>buf</code> starting at index
307 * 0, and the iterator does not use the <code>prng</code>.
308 * <P>
309 * This method uses the algorithm in A. Bissell, Ordered random selection
310 * without replacement, <I>Applied Statistics,</I> 35(1):73-75, 1986.
311 *
312 * @param prng Pseudorandom number generator.
313 * @param n Number of items in the sample.
314 * @param N Number of items in the set.
315 * @param buf Array in which to store the sampled items.
316 * @return Number of sampled items actually stored in <code>buf</code>.
317 * @exception IllegalArgumentException (unchecked exception) Thrown if
318 * <I>n</I> < 0 or <I>N</I> < 0.
319 * @exception NullPointerException (unchecked exception) Thrown if
320 * <code>buf</code> is null.
321 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if
322 * <code>buf.length</code> < <code>n</code>.
323 */
324 public static int withoutReplacement(Random prng,
325 int n,
326 long N,
327 long[] buf) {
328 if (n < 0) {
329 throw new IllegalArgumentException("RandomSample.withoutReplacement(): n < 0 illegal");
330 } else if (N < 0) {
331 throw new IllegalArgumentException("RandomSample.withoutReplacement(): N < 0 illegal");
332 } else if (n < N) {
333 long M = N;
334 long r = N - n;
335 for (int i = 0; i < n; ++i) {
336 double x = prng.nextDouble();
337 double p = 1.0;
338 for (;;) {
339 p = p * r / M;
340 if (p <= x) {
341 buf[i] = N - M;
342 --M;
343 break;
344 } else {
345 --M;
346 --r;
347 }
348 }
349 }
350 return n;
351 } else {
352 for (int i = 0; i < N; ++i) {
353 buf[i] = i;
354 }
355 return (int) N;
356 }
357 }
358
359 // Unit test main program.
360 // /**
361 // * Unit test main program.
362 // */
363 // public static void main
364 // (String[] args)
365 // {
366 // if (args.length != 3)
367 // {
368 // System.err.println ("Usage: java edu.rit.util.RandomSample <n> <N> <seed>");
369 // System.exit (1);
370 // }
371 // int n = Integer.parseInt (args[0]);
372 // int N = Integer.parseInt (args[1]);
373 // long seed = Long.parseLong (args[2]);
374 // Random prng = Random.getInstance (seed);
375 // Iterator<Integer> iter = withoutReplacement (prng, n, N);
376 // while (iter.hasNext()) System.out.printf (" %d", iter.next());
377 // System.out.println();
378 // }
379 }