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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
//:
// \file
// \brief A class which returns an N element subset of the integers [0..M-1]
// \author Tim Cootes
#include "mbl_select_n_from_m.h"
#include <vcl_cassert.h>
#include <vcl_iostream.h>
mbl_select_n_from_m::mbl_select_n_from_m()
: n_(0), m_(0), is_done_(false), use_random_(false)
{
random_.reseed(123746);
}
mbl_select_n_from_m::mbl_select_n_from_m(unsigned int new_n, unsigned int new_m)
: n_(new_n), m_(new_m), is_done_(false), use_random_(false)
{
set_n_m(new_n,new_m);
random_.reseed(123746);
}
//: Reseed randomiser
void mbl_select_n_from_m::reseed(long s)
{
random_.reseed(s);
}
// member functions
void mbl_select_n_from_m::set_n_m(unsigned int new_n, unsigned int new_m)
{
if (new_n>new_m)
{
vcl_cerr<<"mbl_select_n_from_m::set_n_m(): Warning: N>M: nothing selected\n"
<<"N="<<new_n<<" M="<<new_m<<vcl_endl;
is_done_ = true;
}
n_=new_n;
m_=new_m;
index_.resize(n_);
reset();
}
void mbl_select_n_from_m::use_random(bool flag)
{
use_random_=flag;
if (use_random_)
random_.choose_n_from_m(index_,not_index_,n_,m_);
else
reset();
}
bool mbl_select_n_from_m::reset()
{
is_done_ = (n_>m_);
if (is_done_)
return false;
if (use_random_)
{
random_.choose_n_from_m(index_,not_index_,n_,m_);
return true;
}
for (unsigned int i=0;i<n_;++i)
index_[i]=i;
return true;
}
bool mbl_select_n_from_m::next()
{
if (is_done_) return false;
if (use_random_)
{
random_.choose_n_from_m(index_,not_index_,n_,m_);
return true;
}
// quick return if possible; ensures n_-1 >= 0 further down (which is used!)
if (n_==m_ || n_ == 0) { is_done_=true; return false; }
int* index_data = &index_[0];
index_data[n_-1]++; // Increment counter
// Increment previous digit if current one has tripped over limit
unsigned int low_trip_digit = n_; // Lowest digit which has tripped
int start_index=0; // index to start digits when trip occurs
for (unsigned int j=n_-1;j>0;--j)
{
// index_[j] has range j..m-n+j
if (index_data[j]>int(m_-n_+j))
{
index_data[j-1]++;
low_trip_digit=j;
start_index=index_data[j-1]+1;
// Start one above previous digit value
}
}
if (index_data[0]>int(m_-n_))
{
reset(); // to ensure valid data in index_
is_done_=true;
return false;
}
else
if (low_trip_digit<n_)
{
// Reset those above
for (unsigned int i=low_trip_digit;i<n_;i++)
{
index_data[i]=start_index;
start_index++;
}
}
return true;
}
const vcl_vector<int>& mbl_select_n_from_m::subset() const
{
assert (!is_done_);
return index_;
}
const vcl_vector<int>& mbl_select_n_from_m::complement()
{
if (use_random_)
return not_index_;
// not_index_ calculated during call to next();
assert (!is_done_);
if (not_index_.size()!=m_-n_) not_index_.resize(m_-n_);
// Fill not_index_ with values in range 0..m-1 not in index_
// Use fact that index_[i+1]>index_[i]
unsigned int j=0; //index in not_index_ array
unsigned int k=0;
for (unsigned int i=0;i<n_;i++)
{
unsigned int ind_i = index_[i];
while (k<ind_i)
{
not_index_[j]=k;
j++;
k++;
}
++k;
}
// Fill out end of array
while (k<m_)
{
not_index_[j]=k;
j++;
k++;
}
return not_index_;
}
|
