2 * Copyright (c) 2003-2005 The BISON Project
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License version 2 as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Lesser General Public License for more details.
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 import java.util.NoSuchElementException;
22 import java.util.Random;
25 * This class provides a random permutation of indexes. Useful for
26 * random sampling without replacement.
28 public class RandPermutation implements IndexIterator {
31 // ======================= private fields ============================
32 // ===================================================================
35 private int[] buffer = null;
39 private int pointer = 0;
41 private final Random r;
44 // ======================= initialization ============================
45 // ===================================================================
48 /** Sets source of randomness to be used. You need to call
49 * {@link #reset} to fully initialize the object.
50 * @param r Source of randomness
52 public RandPermutation( Random r ) { this.r=r; }
54 // -------------------------------------------------------------------
56 /** Sets source of randomness and initial size. It calls
57 * {@link #setPermutation} to fully initialize the object with a
58 * permuation ready to use.
59 * @param r Source of randomness
60 * @param k size of permutation
62 public RandPermutation( int k, Random r ) {
69 // ======================= public methods ============================
70 // ===================================================================
74 * It calculates a random permutation of the integers from 0 to k-1.
75 * The permutation can be read using method {@link #get}.
76 * If the previous permutation was of the same length, it is more efficient.
77 * Note that after calling this the object is reset, so {@link #next} can
78 * be called k times, even if {@link #get} was called an arbitrary number of
79 * times. Note however that mixing {@link #get} and {@link #next} results in
80 * incorrect behavior for {@link #get} (but {@link #next} works fine).
81 * The idea is to use this method only in connection with {@link #get}.
83 public void setPermutation(int k) {
87 for(int i=len; i>1; i--)
91 buffer[j] = buffer[i-1];
96 // -------------------------------------------------------------------
99 * Returns the ith element of the permutation set by {@link #setPermutation}.
100 * If {@link #next} is called after {@link #setPermutation} and before
101 * this method, then the behavior of this method is unspecified.
103 public int get(int i) {
105 if( i >= len ) throw new IndexOutOfBoundsException();
109 // -------------------------------------------------------------------
112 * It initiates a random permutation of the integers from 0 to k-1.
113 * It does not actually calculate the permutation.
114 * The permutation can be read using method {@link #next}.
115 * Calls to {@link #get} return undefined values, so {@link #next} must be used.
116 * If the previous permutation was of the same length, it is more efficient.
118 public void reset(int k) {
121 if( len == k ) return;
123 if( buffer == null || buffer.length < k )
129 for( int i=0; i<len; ++i ) buffer[i]=i;
132 // -------------------------------------------------------------------
134 /** Next random sample without replacement */
137 if( pointer < 1 ) throw new NoSuchElementException();
139 int j = r.nextInt(pointer);
141 buffer[j] = buffer[pointer-1];
142 buffer[pointer-1] = a;
144 return buffer[--pointer];
147 // -------------------------------------------------------------------
149 public boolean hasNext() { return pointer > 0; }
151 // -------------------------------------------------------------------
154 public static void main( String pars[] ) throws Exception {
156 RandPermutation rp = new RandPermutation(new Random());
160 k = Integer.parseInt(pars[0]);
161 rp.setPermutation(k);
162 for(int i=0; i<k; ++i) System.out.println(rp.get(i));
164 System.out.println();
166 k = Integer.parseInt(pars[1]);
168 while(rp.hasNext()) System.out.println(rp.next());
170 System.out.println();
172 k = Integer.parseInt(pars[2]);
174 while(rp.hasNext()) System.out.println(rp.next());
175 System.out.println(rp.next());