A toolkit for working with phylogenetic data.
v0.24.0
random.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2020 Lucas Czech and HITS gGmbH
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 <cassert>
36 #include <random>
37 #include <stdexcept>
38 #include <string>
39 
40 namespace genesis {
41 namespace utils {
42 
43 // ================================================================================================
44 // Sampling
45 // ================================================================================================
46 
47 std::vector<size_t> select_without_replacement( size_t const k, size_t const n )
48 {
49  // Following http://stackoverflow.com/a/311716/4184258
50  // Knuth's variable names: k=n, n=N
51 
52  std::vector<size_t> result;
53  result.reserve( k );
54 
55  if( k > n ) {
56  throw std::invalid_argument(
57  "Cannot select more unique elements than there are elements: k == " +
58  std::to_string(k) + " > n == " + std::to_string(n) + "."
59  );
60  }
61 
62  auto& engine = Options::get().random_engine();
63  std::uniform_real_distribution<double> distribution( 0.0, 1.0 );
64 
65  size_t t = 0; // total input records dealt with
66  size_t m = 0; // number of items selected so far
67 
68  while( m < k ) {
69  // call a uniform( 0, 1 ) random number generator
70  double const u = distribution( engine );
71 
72  if( (n - t) * u >= k - m ) {
73  t++;
74  } else {
75  assert( t < n );
76  result.push_back( t );
77  t++;
78  m++;
79  }
80  }
81  assert( m == k );
82  assert( result.size() == k );
83 
84  return result;
85 }
86 
87 } // namespace utils
88 } // namespace genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
std::default_random_engine & random_engine()
Returns the default engine for random number generation.
Definition: options.hpp:158
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:47
std::shared_ptr< BaseOutputTarget > to_string(std::string &target_string)
Obtain an output target for writing to a string.
static Options & get()
Returns a single instance of this class.
Definition: options.hpp:60