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

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

Added documentation for Orange.misc.counters.

Line 
1"""
2=======================
3Counters (``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
14class 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
77class 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
137class 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                         
193class 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
251class 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.