1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.rng.sampling; 19 20 import java.util.List; 21 import java.util.Map; 22 import java.util.ArrayList; 23 24 import org.apache.commons.rng.UniformRandomProvider; 25 import org.apache.commons.rng.sampling.distribution.GuideTableDiscreteSampler; 26 import org.apache.commons.rng.sampling.distribution.SharedStateDiscreteSampler; 27 28 /** 29 * Sampling from a collection of items with user-defined 30 * <a href="http://en.wikipedia.org/wiki/Probability_distribution#Discrete_probability_distribution"> 31 * probabilities</a>. 32 * Note that if all unique items are assigned the same probability, 33 * it is much more efficient to use {@link CollectionSampler}. 34 * 35 * <p>Sampling uses {@link UniformRandomProvider#nextDouble()}.</p> 36 * 37 * @param <T> Type of items in the collection. 38 * 39 * @since 1.1 40 */ 41 public class DiscreteProbabilityCollectionSampler<T> 42 implements SharedStateSampler<DiscreteProbabilityCollectionSampler<T>> { 43 /** The error message for an empty collection. */ 44 private static final String EMPTY_COLLECTION = "Empty collection"; 45 /** Collection to be sampled from. */ 46 private final List<T> items; 47 /** Sampler for the probabilities. */ 48 private final SharedStateDiscreteSampler sampler; 49 50 /** 51 * Creates a sampler. 52 * 53 * @param rng Generator of uniformly distributed random numbers. 54 * @param collection Collection to be sampled, with the probabilities 55 * associated to each of its items. 56 * A (shallow) copy of the items will be stored in the created instance. 57 * The probabilities must be non-negative, but zero values are allowed 58 * and their sum does not have to equal one (input will be normalized 59 * to make the probabilities sum to one). 60 * @throws IllegalArgumentException if {@code collection} is empty, a 61 * probability is negative, infinite or {@code NaN}, or the sum of all 62 * probabilities is not strictly positive. 63 */ 64 public DiscreteProbabilityCollectionSampler(UniformRandomProvider rng, 65 Map<T, Double> collection) { 66 if (collection.isEmpty()) { 67 throw new IllegalArgumentException(EMPTY_COLLECTION); 68 } 69 70 // Extract the items and probabilities 71 final int size = collection.size(); 72 items = new ArrayList<T>(size); 73 final double[] probabilities = new double[size]; 74 75 int count = 0; 76 for (final Map.Entry<T, Double> e : collection.entrySet()) { 77 items.add(e.getKey()); 78 probabilities[count++] = e.getValue(); 79 } 80 81 // Delegate sampling 82 sampler = createSampler(rng, probabilities); 83 } 84 85 /** 86 * Creates a sampler. 87 * 88 * @param rng Generator of uniformly distributed random numbers. 89 * @param collection Collection to be sampled. 90 * A (shallow) copy of the items will be stored in the created instance. 91 * @param probabilities Probability associated to each item of the 92 * {@code collection}. 93 * The probabilities must be non-negative, but zero values are allowed 94 * and their sum does not have to equal one (input will be normalized 95 * to make the probabilities sum to one). 96 * @throws IllegalArgumentException if {@code collection} is empty or 97 * a probability is negative, infinite or {@code NaN}, or if the number 98 * of items in the {@code collection} is not equal to the number of 99 * provided {@code probabilities}. 100 */ 101 public DiscreteProbabilityCollectionSampler(UniformRandomProvider rng, 102 List<T> collection, 103 double[] probabilities) { 104 if (collection.isEmpty()) { 105 throw new IllegalArgumentException(EMPTY_COLLECTION); 106 } 107 final int len = probabilities.length; 108 if (len != collection.size()) { 109 throw new IllegalArgumentException("Size mismatch: " + 110 len + " != " + 111 collection.size()); 112 } 113 // Shallow copy the list 114 items = new ArrayList<T>(collection); 115 // Delegate sampling 116 sampler = createSampler(rng, probabilities); 117 } 118 119 /** 120 * @param rng Generator of uniformly distributed random numbers. 121 * @param source Source to copy. 122 */ 123 private DiscreteProbabilityCollectionSampler(UniformRandomProvider rng, 124 DiscreteProbabilityCollectionSampler<T> source) { 125 this.items = source.items; 126 this.sampler = source.sampler.withUniformRandomProvider(rng); 127 } 128 129 /** 130 * Picks one of the items from the collection passed to the constructor. 131 * 132 * @return a random sample. 133 */ 134 public T sample() { 135 return items.get(sampler.sample()); 136 } 137 138 /** 139 * {@inheritDoc} 140 * 141 * @since 1.3 142 */ 143 @Override 144 public DiscreteProbabilityCollectionSampler<T> withUniformRandomProvider(UniformRandomProvider rng) { 145 return new DiscreteProbabilityCollectionSampler<T>(rng, this); 146 } 147 148 /** 149 * Creates the sampler of the enumerated probability distribution. 150 * 151 * @param rng Generator of uniformly distributed random numbers. 152 * @param probabilities Probability associated to each item. 153 * @return the sampler 154 */ 155 private static SharedStateDiscreteSampler createSampler(UniformRandomProvider rng, 156 double[] probabilities) { 157 return GuideTableDiscreteSampler.of(rng, probabilities); 158 } 159 }