#
source:
orange/Orange/misc/counters.py
@
9871:79b722e3440a

Revision 9871:79b722e3440a, 8.6 KB checked in by crt.gorup@…, 2 years ago (diff) |
---|

Line | |
---|---|

1 | """ |

2 | ======================= |

3 | Counters (``counters``) |

4 | ======================= |

5 | |

6 | .. index:: misc |

7 | .. index:: |

8 | single: misc; counters |

9 | |

10 | :class:`Orange.misc.counters` contains a bunch of classes that generate sequences of various kinds. |

11 | |

12 | """ |

13 | |

14 | class BooleanCounter: |

15 | """ |

16 | A class which represents a boolean counter. The constructor is given the number of bits and during the |

17 | iteration the counter returns a list of that length with 0 and 1's in it. |

18 | |

19 | One way to use the counter is within a for-loop: |

20 | |

21 | >>> for r in Orange.misc.counters.BooleanCounter(3): |

22 | ... print r |

23 | [0, 0, 0] |

24 | [0, 0, 1] |

25 | [0, 1, 0] |

26 | [0, 1, 1] |

27 | [1, 0, 0] |

28 | [1, 0, 1] |

29 | [1, 1, 0] |

30 | [1, 1, 1] |

31 | |

32 | You can also call it manually. |

33 | |

34 | >>> r = Orange.misc.counters.BooleanCounter(3) |

35 | >>> r.next() |

36 | [0, 0, 0] |

37 | >>> r.next() |

38 | [0, 0, 1] |

39 | >>> r.next() |

40 | [0, 1, 0] |

41 | |

42 | .. attribute:: state |

43 | |

44 | The current counter state (the last result of a call to next) is also stored as attribute attribute. |

45 | |

46 | """ |

47 | |

48 | def __init__(self, bits): |

49 | """ |

50 | :param bits: Number of bits. |

51 | :type bits: int |

52 | """ |

53 | self.bits = bits |

54 | self.state = None |

55 | |

56 | def __iter__(self): |

57 | if self.state: |

58 | return self |

59 | else: |

60 | return BooleanCounter(self.bits) |

61 | |

62 | def next(self): |

63 | """Return the next state of the counter.""" |

64 | if self.state: |

65 | for bit in range(self.bits-1, -1, -1): |

66 | self.state[bit] = (self.state[bit]+1) % 2 |

67 | if self.state[bit]: |

68 | break |

69 | else: |

70 | self.state = None |

71 | else: |

72 | self.state = [0]*self.bits |

73 | if not self.state: |

74 | raise StopIteration, "BooleanCounter: counting finished" |

75 | return self.state |

76 | |

77 | class LimitedCounter: |

78 | """ |

79 | This class is similar to :class:`~Orange.misc.counters.BooleanCounter` except that the digits do not count |

80 | from 0 to 1, but to the limits that are specified individually for each digit. |

81 | |

82 | >>> for t in Orange.misc.counters.LimitedCounter([3, 5, 2]): |

83 | ... print t |

84 | [0, 0, 0] |

85 | [0, 0, 1] |

86 | [0, 1, 0] |

87 | [0, 1, 1] |

88 | [0, 2, 0] |

89 | [0, 2, 1] |

90 | [0, 3, 0] |

91 | [0, 3, 1] |

92 | [0, 4, 0] |

93 | [0, 4, 1] |

94 | [1, 0, 0] |

95 | [1, 0, 1] |

96 | [1, 1, 0] |

97 | [1, 1, 1] |

98 | |

99 | .. attribute:: state |

100 | |

101 | The current counter state (the last result of a call to next) is also stored as attribute attribute. |

102 | """ |

103 | |

104 | def __init__(self, limits): |

105 | """ |

106 | :param limits: Domain size per bit position. |

107 | :type limits: list |

108 | """ |

109 | self.limits = limits |

110 | self.state = None |

111 | |

112 | def __iter__(self): |

113 | if self.state: |

114 | return self |

115 | else: |

116 | return LimitedCounter(self.limits) |

117 | |

118 | def next(self): |

119 | """Return the next state of the counter.""" |

120 | if self.state: |

121 | i = len(self.limits)-1 |

122 | while (i>=0) and (self.state[i]==self.limits[i]-1): |

123 | self.state[i] = 0 |

124 | i -= 1 |

125 | if i==-1: |

126 | self.state = None |

127 | else: |

128 | self.state[i] += 1 |

129 | else: |

130 | self.state = [0]*len(self.limits) |

131 | |

132 | if not self.state: |

133 | raise StopIteration, "LimitedCounter: counting finished" |

134 | |

135 | return self.state |

136 | |

137 | class MofNCounter: |

138 | """ |

139 | Counter returns all consecutive subset lists of length ``m`` out of ``n`` where ``m`` <= ``n``. |

140 | |

141 | >>> for t in Orange.misc.counters.MofNCounter(3,7): |

142 | ... print t |

143 | ... |

144 | [0, 1, 2] |

145 | [1, 2, 3] |

146 | [2, 3, 4] |

147 | [3, 4, 5] |

148 | [4, 5, 6] |

149 | |

150 | .. attribute:: state |

151 | |

152 | The current counter state (the last result of a call to next) is also stored as attribute attribute. |

153 | """ |

154 | |

155 | def __init__(self, m, n): |

156 | """ |

157 | :param m: Length of subset list. |

158 | :type m: int |

159 | |

160 | :param n: Total length. |

161 | :type n: int |

162 | """ |

163 | if m > n: |

164 | raise TypeError, "Number of selected items exceeds the number of items" |

165 | |

166 | self.state = None |

167 | self.m = m |

168 | self.n = n |

169 | |

170 | def __iter__(self): |

171 | if self.state: |

172 | return self |

173 | else: |

174 | return MofNCounter(self.m, self.n) |

175 | |

176 | def next(self): |

177 | """Return the next state of the counter.""" |

178 | if self.state: |

179 | m, n, state = self.m, self.n, self.state |

180 | for place in range(m-1, -1, -1): |

181 | if state[place] + m-1-place < n-1: |

182 | state[place] += 1 |

183 | for place in range(place+1, m): |

184 | state[place] = state[place-1] + 1 |

185 | break |

186 | else: |

187 | self.state = None |

188 | raise StopIteration, "MofNCounter: counting finished" |

189 | else: |

190 | self.state = range(self.m) |

191 | return self.state[:] |

192 | |

193 | class NondecreasingCounter: |

194 | """ |

195 | Nondecreasing counter generates all non-decreasing integer sequences in which no numbers are skipped, |

196 | that is, if n is in the sequence, the sequence also includes all numbers between 0 and n. For instance, |

197 | [0, 0, 1, 0] is illegal since it decreases, and [0, 0, 2, 2] is illegal since it has 2 without having 1 |

198 | first. Or, with an example |

199 | |

200 | Nondecreasing counter generates all non-decreasing integer sequences in which no numbers are skipped, |

201 | that is, if ``n`` is in the sequence, the sequence also includes all numbers between 0 and ``n``. For instance, |

202 | [0, 0, 1, 0] is illegal since it decreases, and [0, 0, 2, 2] is illegal since it has 2 without having 1 first. |

203 | Or, with an example |

204 | |

205 | >>> for t in Orange.misc.counters.NondecreasingCounter(4): |

206 | ... print t |

207 | ... |

208 | [0, 0, 0, 0] |

209 | [0, 0, 0, 1] |

210 | [0, 0, 1, 1] |

211 | [0, 0, 1, 2] |

212 | [0, 1, 1, 1] |

213 | [0, 1, 1, 2] |

214 | [0, 1, 2, 2] |

215 | [0, 1, 2, 3] |

216 | |

217 | .. attribute:: state |

218 | |

219 | The current counter state (the last result of a call to next) is also stored as attribute attribute. |

220 | """ |

221 | def __init__(self, places): |

222 | """ |

223 | :param places: Number of places. |

224 | :type places: int |

225 | """ |

226 | self.state=None |

227 | self.subcounter=None |

228 | self.places=places |

229 | |

230 | def __iter__(self): |

231 | if self.state: |

232 | return self |

233 | else: |

234 | return NondecreasingCounter(self.places) |

235 | |

236 | def next(self): |

237 | """Return the next state of the counter.""" |

238 | if not self.subcounter: |

239 | self.subcounter=BooleanCounter(self.places-1) |

240 | if self.subcounter.next(): |

241 | self.state=[0] |

242 | for add_one in self.subcounter.state: |

243 | self.state.append(self.state[-1]+add_one) |

244 | else: |

245 | self.state=None |

246 | if not self.state: |

247 | raise StopIteration, "NondecreasingCounter: counting finished" |

248 | return self.state |

249 | |

250 | |

251 | class CanonicFuncCounter: |

252 | """ |

253 | Returns all sequences of a given length where no numbers are skipped (see below) and none of |

254 | the generated sequence is equal to another if only the labels are changed. For instance, [0, 2, 2, 1] |

255 | and [1, 0, 0, 2] are considered equivalent: if we take the former and replace 0 by 1, 2 |

256 | by 0 and 1 by 2 we get the second list. |

257 | |

258 | The sequences generated are equivalent to all possible functions from a set of cardinality of the sequences length. |

259 | |

260 | >>> for t in Orange.misc.counters.CanonicFuncCounter(4): |

261 | ... print t |

262 | ... |

263 | [0, 0, 0, 0] |

264 | [0, 0, 0, 1] |

265 | [0, 0, 1, 0] |

266 | [0, 0, 1, 1] |

267 | [0, 0, 1, 2] |

268 | [0, 1, 0, 0] |

269 | [0, 1, 0, 1] |

270 | [0, 1, 0, 2] |

271 | [0, 1, 1, 0] |

272 | [0, 1, 1, 1] |

273 | [0, 1, 1, 2] |

274 | [0, 1, 2, 0] |

275 | [0, 1, 2, 1] |

276 | [0, 1, 2, 2] |

277 | [0, 1, 2, 3] |

278 | |

279 | .. attribute:: state |

280 | |

281 | The current counter state (the last result of a call to next) is also stored as attribute attribute. |

282 | """ |

283 | def __init__(self, places): |

284 | """ |

285 | :param places: Number of places. |

286 | :type places: int |

287 | """ |

288 | self.places = places |

289 | self.state = None |

290 | |

291 | def __iter__(self): |

292 | if self.state: |

293 | return self |

294 | else: |

295 | return CanonicFuncCounter(self.places) |

296 | |

297 | def next(self): |

298 | """Return the next state of the counter.""" |

299 | if self.state: |

300 | i = self.places-1 |

301 | while (i>0) and (self.state[i]==max(self.state[:i])+1): |

302 | self.state[i] = 0 |

303 | i -= 1 |

304 | if i: |

305 | self.state[i] += 1 |

306 | else: |

307 | self.state=None |

308 | else: |

309 | self.state = [0]*self.places |

310 | if not self.state: |

311 | raise StopIteration, "CanonicFuncCounter: counting finished" |

312 | return self.state |

**Note:**See TracBrowser for help on using the repository browser.