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 weighted random permutation of indexes.
26 * Useful for weighted random sampling without replacement.
27 * The next sample is taken according to the weights given as a parameter
28 * to {@link #reset(int)}.
29 * The weights work as follows.
30 * The first sample is drawn according to the probability distribution
31 * defined by the (normalized) weights.
32 * After this the remaining k-1 elements and the associated k-1
33 * (re-normalized) weights
34 * define a new probability distribution, according to which the 2nd element
35 * is drawn, and so on.
37 public class WeightedRandPerm implements IndexIterator {
40 // ======================= private fields ============================
41 // ===================================================================
43 /** Holds the weights that are used to initialize the permutation */
44 private final double[] w;
46 /** Holds the sum of the weights until the given index, inclusive. */
47 private final double[] wsum;
49 private int[] buffer = null;
51 /** Working array for calculating the permutation */
52 private double[] weights = null;
56 private int pointer = 0;
58 private double sum = 0.0;
60 private final Random r;
63 // ======================= initialization ============================
64 // ===================================================================
67 /** Set the source of randomness to use and the weights. You need to call
68 * {@link #reset} to fully initialize the object.
69 * @param r source of randomness
70 * @param weights The array that holds the weights for the calculation of the
71 * permutation. The length of the array will be an upper bound on the
72 * parameter {@link #reset} accepts. If {@link #reset} is called with a
73 * parameter less than the length of weights, the prefix of the same length
75 * The vector elements must be positive, that is, zero is not accepted either.
77 public WeightedRandPerm( Random r, double[] weights ) {
81 wsum = weights.clone();;
82 this.weights = new double[w.length];
83 buffer = new int[w.length];
85 for(int i=0; i<w.length; ++i)
87 if( w[i] <= 0.0 ) throw new IllegalArgumentException(
88 "weights should be positive: w["+i+"]="+w[i]);
91 for(int i=1; i<w.length; ++i) wsum[i]+=wsum[i-1];
95 // ======================= public methods ============================
96 // ===================================================================
100 * It initiates a random weighted permutation of the integeres from 0 to k-1.
101 * It does not actually calculate the permutation.
102 * The permutation can be read using method {@link #next}.
103 * If the previous permutation was of the same length, it is more efficient.
104 * The weights set at construction time work as follows.
105 * The first sample is drawn according to the probability distribution
106 * defined by the (normalized) weights.
107 * After this the remaining k-1 elements and the associated k-1
108 * (re-normalized) weights
109 * define a new probability distribution, according to which the 2nd element
110 * is drawn, and so on.
111 * @param k the set is defined as 0,...,k-1
113 public void reset(int k) {
115 if( k<0 || k>w.length )
116 throw new IllegalArgumentException(
117 "k should be non-negative and <= "+w.length);
124 // we need to initialize weights and buffer
125 for(int i=0; i<k; ++i)
134 // -------------------------------------------------------------------
137 * The first sample is drawn according to the probability distribution
138 * defined by the (normalized) weights.
139 * After this the remaining k-1 elements and the associated k-1
140 * (re-normalized) weights
141 * define a new probability distribution, according to which the 2nd element
142 * is drawn, and so on.
147 if( pointer < 1 ) throw new NoSuchElementException();
149 double d = sum*r.nextDouble();
151 double tmp = weights[i-1];
152 while( tmp < d && i>1 ) tmp += weights[--i-1];
154 // now i-1 is the selected element, we shift it to next position
156 double b = weights[i-1];
157 buffer[i-1] = buffer[pointer-1];
158 weights[i-1] = weights[pointer-1];
159 buffer[pointer-1] = a;
160 weights[pointer-1] = b;
163 return buffer[--pointer];
166 // -------------------------------------------------------------------
168 public boolean hasNext() { return pointer > 0; }
170 // -------------------------------------------------------------------
173 public static void main( String pars[] ) throws Exception {
177 double w[] = new double[k];
178 for(int i=0; i<k; ++i) w[i] = Double.parseDouble(pars[i]);
180 WeightedRandPerm rp = new WeightedRandPerm(new Random(),w);
182 for(int i=0; i<1000; ++i)
184 if(i%2==0) rp.reset(k);
185 if(i%2==1) rp.reset(k-1);
186 while(rp.hasNext()) System.out.print(rp.next()+" ");
187 System.out.println();
190 System.out.println();