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