A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
random.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2017 Lucas Czech
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  Contact:
19  Lucas Czech <lucas.czech@h-its.org>
20  Exelixis Lab, Heidelberg Institute for Theoretical Studies
21  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
22 */
23 
32 
34 
35 #include <random>
36 #include <stdexcept>
37 #include <string>
38 
39 namespace genesis {
40 namespace utils {
41 
42 // ================================================================================================
43 // Sampling
44 // ================================================================================================
45 
46 std::vector<size_t> select_without_replacement( size_t const k, size_t const n )
47 {
48  // Following http://stackoverflow.com/a/311716/4184258
49  // Knuth's variable names: n=N, k=n
50 
51  std::vector<size_t> result;
52 
53  if( k > n ) {
54  throw std::invalid_argument(
55  "Cannot select more unique elements than there are elements: k == " +
56  std::to_string(k) + " > n == " + std::to_string(n) + "."
57  );
58  }
59 
60  auto& engine = Options::get().random_engine();
61  std::uniform_real_distribution<double> distribution( 0.0, 1.0 );
62 
63  size_t t = 0; // total input records dealt with
64  size_t m = 0; // number of items selected so far
65  double u;
66 
67  while( m < k ) {
68  // call a uniform( 0, 1 ) random number generator
69  u = distribution( engine );
70 
71  if( (n - t) * u >= k - m ) {
72  t++;
73  } else {
74  result.push_back( t );
75  t++;
76  m++;
77  }
78  }
79 
80  return result;
81 }
82 
83 } // namespace utils
84 } // namespace genesis
std::string to_string(T const &v)
Return a string representation of a given value.
Definition: string.hpp:300
std::default_random_engine & random_engine()
Returns the default engine for random number generation.
Definition: options.hpp:151
std::vector< size_t > select_without_replacement(size_t const k, size_t const n)
Select k many unique numbers out of the range [ 0, n ).
Definition: random.cpp:46
static Options & get()
Returns a single instance of this class.
Definition: options.hpp:59