View Javadoc
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 }