source: orange/Orange/utils/counters.py @ 10582:180f600dfb15

Revision 10582:180f600dfb15, 8.5 KB checked in by markotoplak, 2 years ago (diff)

Orange.misc to Orange.utils move: some more fixes.

Line 
1"""
2=======================
3Counters (``counters``)
4=======================
5
6.. index:: utils
7.. index::
8     single: utils; counters
9
10:class:`Orange.utils.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 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 = 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.utils.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 LimitedCounter([3, 5]):
83    ...     print t
84    [0, 0]
85    [0, 1]
86    [0, 2]
87    [0, 3]
88    [0, 4]
89    [1, 0]
90    [1, 1]
91    [1, 2]
92    [1, 3]
93    [1, 4]
94    [2, 0]
95    [2, 1]
96    [2, 2]
97    [2, 3]
98    [2, 4]
99
100    .. attribute:: state
101
102        The current counter state (the last result of a call to next) is also stored as attribute attribute.
103    """
104   
105    def __init__(self, limits):
106        """
107            :param limits: Domain size per bit position.
108            :type limits: list
109        """
110        self.limits = limits
111        self.state = None
112       
113    def __iter__(self):
114        if self.state:
115            return self
116        else:
117            return LimitedCounter(self.limits)
118
119    def next(self):
120        """Return the next state of the counter."""
121        if self.state:
122            i = len(self.limits)-1
123            while (i>=0) and (self.state[i]==self.limits[i]-1):
124                self.state[i] = 0
125                i -= 1
126            if i==-1:
127                self.state = None
128            else:
129                self.state[i] += 1
130        else:
131            self.state = [0]*len(self.limits)
132   
133        if not self.state:
134            raise StopIteration, "LimitedCounter: counting finished"
135
136        return self.state
137
138class MofNCounter:
139    """
140    Counter returns all consecutive subset lists of length ``m`` out of ``n`` where ``m`` <= ``n``.
141
142    >>> for t in MofNCounter(3,7):
143    ...     print t
144    ...
145    [0, 1, 2]
146    [1, 2, 3]
147    [2, 3, 4]
148    [3, 4, 5]
149    [4, 5, 6]
150
151    .. attribute:: state
152
153        The current counter state (the last result of a call to next) is also stored as attribute attribute.
154    """
155   
156    def __init__(self, m, n):
157        """
158        :param m: Length of subset list.
159        :type m: int
160
161        :param n: Total length.
162        :type n: int
163        """
164        if m > n:
165            raise TypeError, "Number of selected items exceeds the number of items"
166               
167        self.state = None
168        self.m = m
169        self.n = n
170               
171    def __iter__(self):
172        if self.state:
173            return self
174        else:
175            return MofNCounter(self.m, self.n)
176               
177    def next(self):
178        """Return the next state of the counter."""
179        if self.state:
180            m, n, state = self.m, self.n, self.state
181            for place in range(m-1, -1, -1):
182                if state[place] + m-1-place < n-1:
183                    state[place] += 1
184                    for place in range(place+1, m):
185                        state[place] = state[place-1] + 1
186                        break
187                else:
188                    self.state = None
189                    raise StopIteration, "MofNCounter: counting finished"
190        else:
191            self.state = range(self.m)
192        return self.state[:]
193                         
194class NondecreasingCounter:
195    """
196    Nondecreasing counter generates all non-decreasing integer sequences in which no numbers are skipped,
197    that is, if n is in the sequence, the sequence also includes all numbers between 0 and n. For instance,
198    [0, 0, 1, 0] is illegal since it decreases, and [0, 0, 2, 2] is illegal since it has 2 without having 1
199    first. Or, with an example
200
201    Nondecreasing counter generates all non-decreasing integer sequences in which no numbers are skipped,
202    that is, if ``n`` is in the sequence, the sequence also includes all numbers between 0 and ``n``. For instance,
203    [0, 0, 1, 0] is illegal since it decreases, and [0, 0, 2, 2] is illegal since it has 2 without having 1 first.
204    Or, with an example
205
206    >>> for t in NondecreasingCounter(4):
207    ...     print t
208    ...
209    [0, 0, 0, 0]
210    [0, 0, 0, 1]
211    [0, 0, 1, 1]
212    [0, 0, 1, 2]
213    [0, 1, 1, 1]
214    [0, 1, 1, 2]
215    [0, 1, 2, 2]
216    [0, 1, 2, 3]
217
218    .. attribute:: state
219
220        The current counter state (the last result of a call to next) is also stored as attribute attribute.
221    """
222    def __init__(self, places):
223        """
224            :param places: Number of places.
225            :type places: int
226        """
227        self.state=None
228        self.subcounter=None
229        self.places=places
230
231    def __iter__(self):
232        if self.state:
233            return self
234        else:
235            return NondecreasingCounter(self.places)
236
237    def next(self):
238        """Return the next state of the counter."""
239        if not self.subcounter:
240            self.subcounter=BooleanCounter(self.places-1)
241        if self.subcounter.next():
242            self.state=[0]
243            for add_one in self.subcounter.state:
244                self.state.append(self.state[-1]+add_one)
245        else:
246            self.state=None
247        if not self.state:
248            raise StopIteration, "NondecreasingCounter: counting finished"
249        return self.state
250
251
252class CanonicFuncCounter:
253    """
254    Returns all sequences of a given length where no numbers are skipped (see below) and none of
255    the generated sequence is equal to another if only the labels are changed. For instance, [0, 2, 2, 1]
256    and [1, 0, 0, 2] are considered equivalent: if we take the former and replace 0 by 1, 2
257    by 0 and 1 by 2 we get the second list.
258
259    The sequences generated are equivalent to all possible functions from a set of cardinality of the sequences length.
260
261    >>> for t in CanonicFuncCounter(4):
262    ...     print t
263    ...
264    [0, 0, 0, 0]
265    [0, 0, 0, 1]
266    [0, 0, 1, 0]
267    [0, 0, 1, 1]
268    [0, 0, 1, 2]
269    [0, 1, 0, 0]
270    [0, 1, 0, 1]
271    [0, 1, 0, 2]
272    [0, 1, 1, 0]
273    [0, 1, 1, 1]
274    [0, 1, 1, 2]
275    [0, 1, 2, 0]
276    [0, 1, 2, 1]
277    [0, 1, 2, 2]
278    [0, 1, 2, 3]
279
280    .. attribute:: state
281
282        The current counter state (the last result of a call to next) is also stored as attribute attribute.
283    """
284    def __init__(self, places):
285        """
286            :param places: Number of places.
287            :type places: int
288        """
289        self.places = places
290        self.state = None
291
292    def __iter__(self):
293        if self.state:
294            return self
295        else:
296            return CanonicFuncCounter(self.places)
297
298    def next(self):
299        """Return the next state of the counter."""
300        if self.state:
301            i = self.places-1
302            while (i>0) and (self.state[i]==max(self.state[:i])+1):
303                self.state[i] = 0
304                i -= 1
305            if i:
306                self.state[i] += 1
307            else:
308                self.state=None
309        else:
310            self.state = [0]*self.places
311        if not self.state:
312            raise StopIteration, "CanonicFuncCounter: counting finished"
313        return self.state
Note: See TracBrowser for help on using the repository browser.