001/* 002 * RandomSample.java 003 * Copyright (c) 2002 004 * 005 * This program is free software; you can redistribute it and/or 006 * modify it under the terms of the GNU General Public License 007 * as published by the Free Software Foundation; either version 2 008 * of the License, or any later version. 009 * 010 * This program is distributed in the hope that it will be useful, 011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 013 * GNU General Public License for more details. 014 * 015 * You should have received a copy of the GNU General Public License 016 * along with this program; if not, write to the Free Software 017 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 018 */ 019 020package ca.bc.webarts.widgets.random; 021 022import java.util.Random; 023 024/** 025 * This class allows you to randomly select n numbers from 1 to N. The 026 * algorithm used here is described in Knuth, TAOCP, volume 2, second print, 027 * section 3.4.2, algorithm S on page 122 (page 142 in the third edition) 028 * (C) 2000, Laurentiu Cristofor (laur72_98@yahoo.com) 029 * 030 * @created May 19, 2002 031 */ 032 033public class RandomSample 034{ 035 // I use the variable naming from Knuth ! 036 private long N; 037 private int n; 038 private Random rand; 039 040 041 /** 042 * Create a new generator of random samples of <code>n</code> distinct values 043 * from the numbers 1 to <code>N</code>. 044 * 045 * @param N specifies the range from which we 046 * want a sample, the range will be 1...<code>N</code>. 047 * @param n specifies the size of the sample, the 048 * sample will contain distinct values in the range specified by <code>N</code> 049 * . 050 */ 051 public RandomSample(long N, int n) 052 { 053 if (N < 1 || n < 1 || N < n) 054 { 055 throw new IllegalArgumentException("You must provide n and N s.t. 0 < n <= N"); 056 } 057 058 this.N = N; 059 this.n = n; 060 rand = new Random(); 061 } 062 063 064 /** 065 * Return a random sample. 066 * 067 * @return an array of <code>n</code> numbers sampled from the numbers 1... 068 * <code>N</code>. 069 */ 070 public long[] nextSample() 071 { 072 long[] sample = new long[n]; 073 int i = 0; 074 075 // S1. [Initialize] 076 long t = 0; 077 // how many we have seen 078 int m = 0; 079 // how many we have selected 080 while (true) 081 { 082 // S2. [Generate U] 083 double U = rand.nextDouble(); 084 // S3. [Test] 085 if ((N - t) * U >= n - m) 086 { 087 // S5. [Skip] 088 t = t + 1; 089 } 090 else 091 { 092 // S4. [Select] 093 sample[i++] = t + 1; 094 m = m + 1; 095 t = t + 1; 096 097 if (m < n) 098 { 099 ; 100 } 101 else 102 { 103 // sample complete ! 104 return sample; 105 } 106 } 107 } 108 } 109 110 111 /** 112 * The main program for the RandomSample class 113 * 114 * @param args The command line arguments 115 */ 116 public static void main(String[] args) 117 { 118 RandomSample rs = new RandomSample(100, 7); 119 120 for (int i = 0; i < 10; i++) 121 { 122 long[] sample = rs.nextSample(); 123 for (int j = 0; j < sample.length; j++) 124 { 125 System.out.print(sample[j] + " "); 126 } 127 System.out.println(""); 128 } 129 } 130} 131 132