1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
//:
// \file
// \brief Randomly select n from m integers without replacement
// \author Tim Cootes
#include "mbl_random_n_from_m.h"
#include <vcl_iostream.h>
#include <vcl_cstdlib.h>
mbl_random_n_from_m::mbl_random_n_from_m()
{
}
void mbl_random_n_from_m::reseed(long new_seed)
{
mz_random_.reseed(new_seed);
}
//: Select n integers from range [0,m-1], without replacement
void mbl_random_n_from_m::choose_n_from_m(vcl_vector<unsigned>& choice,
unsigned int n, unsigned int m)
{
if (n>m)
{
vcl_cerr<<"mbl_random_n_from_m::choose_n_from_m() : Can't choose "<<n
<<" different integers from "<<m<<vcl_endl;
vcl_abort();
}
if (choice.size()!=n) choice.resize(n);
if (used_.size()<m) used_.resize(m);
for (unsigned int i=0;i<m;i++) used_[i] = false;
for (unsigned int i=0;i<n;i++)
{
// Select a random integer in a reducing range
int j = mz_random_.lrand32(m-i-1);
// Find the j'th un-used integer
int k2=-1;
for (int k1=0; k1<=j; ++k1)
{
// Move k2 to next unused
++k2;
while (used_[k2])
++k2;
}
choice[i] = k2;
used_[k2] = true;
}
}
//: Select n integers from range [0,m-1], without replacement
void mbl_random_n_from_m::choose_n_from_m(vcl_vector<unsigned>& chosen,
vcl_vector<unsigned>& not_chosen,
unsigned int n, unsigned int m)
{
choose_n_from_m(chosen,n,m);
// The used array contains details of choice.
unsigned int n1 = m-n; // n is guaranteed <= m
if (not_chosen.size()!=n1) not_chosen.resize(n1);
for (unsigned int i=0,j=0;i<m;i++)
if (!used_[i])
not_chosen[j++]=i;
}
//: Select n integers from range [0,m-1], without replacement
void mbl_random_n_from_m::choose_n_from_m(vcl_vector<int>& choice,
unsigned int n, unsigned int m)
{
if (n>m)
{
vcl_cerr<<"mbl_random_n_from_m::choose_n_from_m() : Can't choose "<<n
<<" different integers from "<<m<<vcl_endl;
vcl_abort();
}
if (choice.size()!=n) choice.resize(n);
if (used_.size()<m) used_.resize(m);
for (unsigned int i=0;i<m;i++) used_[i] = false;
for (unsigned int i=0;i<n;i++)
{
// Select a random integer in a reducing range
int j = mz_random_.lrand32(m-i-1);
// Find the j'th un-used integer
int k2=-1;
for (int k1=0; k1<=j; ++k1)
{
// Move k2 to next unused
++k2;
while (used_[k2])
++k2;
}
choice[i] = k2;
used_[k2] = true;
}
}
//: Select n integers from range [0,m-1], without replacement
void mbl_random_n_from_m::choose_n_from_m(vcl_vector<int>& chosen,
vcl_vector<int>& not_chosen,
unsigned int n, unsigned int m)
{
choose_n_from_m(chosen,n,m);
// The used array contains details of choice.
unsigned int n1 = m-n; // n is guaranteed <= m
if (not_chosen.size()!=n1) not_chosen.resize(n1);
for (unsigned int i=0,j=0;i<m;i++)
if (!used_[i])
not_chosen[j++]=i;
}
|
