Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/graycode.py: 26%
95 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1from sympy.core import Basic, Integer
3import random
6class GrayCode(Basic):
7 """
8 A Gray code is essentially a Hamiltonian walk on
9 a n-dimensional cube with edge length of one.
10 The vertices of the cube are represented by vectors
11 whose values are binary. The Hamilton walk visits
12 each vertex exactly once. The Gray code for a 3d
13 cube is ['000','100','110','010','011','111','101',
14 '001'].
16 A Gray code solves the problem of sequentially
17 generating all possible subsets of n objects in such
18 a way that each subset is obtained from the previous
19 one by either deleting or adding a single object.
20 In the above example, 1 indicates that the object is
21 present, and 0 indicates that its absent.
23 Gray codes have applications in statistics as well when
24 we want to compute various statistics related to subsets
25 in an efficient manner.
27 Examples
28 ========
30 >>> from sympy.combinatorics import GrayCode
31 >>> a = GrayCode(3)
32 >>> list(a.generate_gray())
33 ['000', '001', '011', '010', '110', '111', '101', '100']
34 >>> a = GrayCode(4)
35 >>> list(a.generate_gray())
36 ['0000', '0001', '0011', '0010', '0110', '0111', '0101', '0100', \
37 '1100', '1101', '1111', '1110', '1010', '1011', '1001', '1000']
39 References
40 ==========
42 .. [1] Nijenhuis,A. and Wilf,H.S.(1978).
43 Combinatorial Algorithms. Academic Press.
44 .. [2] Knuth, D. (2011). The Art of Computer Programming, Vol 4
45 Addison Wesley
48 """
50 _skip = False
51 _current = 0
52 _rank = None
54 def __new__(cls, n, *args, **kw_args):
55 """
56 Default constructor.
58 It takes a single argument ``n`` which gives the dimension of the Gray
59 code. The starting Gray code string (``start``) or the starting ``rank``
60 may also be given; the default is to start at rank = 0 ('0...0').
62 Examples
63 ========
65 >>> from sympy.combinatorics import GrayCode
66 >>> a = GrayCode(3)
67 >>> a
68 GrayCode(3)
69 >>> a.n
70 3
72 >>> a = GrayCode(3, start='100')
73 >>> a.current
74 '100'
76 >>> a = GrayCode(4, rank=4)
77 >>> a.current
78 '0110'
79 >>> a.rank
80 4
82 """
83 if n < 1 or int(n) != n:
84 raise ValueError(
85 'Gray code dimension must be a positive integer, not %i' % n)
86 n = Integer(n)
87 args = (n,) + args
88 obj = Basic.__new__(cls, *args)
89 if 'start' in kw_args:
90 obj._current = kw_args["start"]
91 if len(obj._current) > n:
92 raise ValueError('Gray code start has length %i but '
93 'should not be greater than %i' % (len(obj._current), n))
94 elif 'rank' in kw_args:
95 if int(kw_args["rank"]) != kw_args["rank"]:
96 raise ValueError('Gray code rank must be a positive integer, '
97 'not %i' % kw_args["rank"])
98 obj._rank = int(kw_args["rank"]) % obj.selections
99 obj._current = obj.unrank(n, obj._rank)
100 return obj
102 def next(self, delta=1):
103 """
104 Returns the Gray code a distance ``delta`` (default = 1) from the
105 current value in canonical order.
108 Examples
109 ========
111 >>> from sympy.combinatorics import GrayCode
112 >>> a = GrayCode(3, start='110')
113 >>> a.next().current
114 '111'
115 >>> a.next(-1).current
116 '010'
117 """
118 return GrayCode(self.n, rank=(self.rank + delta) % self.selections)
120 @property
121 def selections(self):
122 """
123 Returns the number of bit vectors in the Gray code.
125 Examples
126 ========
128 >>> from sympy.combinatorics import GrayCode
129 >>> a = GrayCode(3)
130 >>> a.selections
131 8
132 """
133 return 2**self.n
135 @property
136 def n(self):
137 """
138 Returns the dimension of the Gray code.
140 Examples
141 ========
143 >>> from sympy.combinatorics import GrayCode
144 >>> a = GrayCode(5)
145 >>> a.n
146 5
147 """
148 return self.args[0]
150 def generate_gray(self, **hints):
151 """
152 Generates the sequence of bit vectors of a Gray Code.
154 Examples
155 ========
157 >>> from sympy.combinatorics import GrayCode
158 >>> a = GrayCode(3)
159 >>> list(a.generate_gray())
160 ['000', '001', '011', '010', '110', '111', '101', '100']
161 >>> list(a.generate_gray(start='011'))
162 ['011', '010', '110', '111', '101', '100']
163 >>> list(a.generate_gray(rank=4))
164 ['110', '111', '101', '100']
166 See Also
167 ========
169 skip
171 References
172 ==========
174 .. [1] Knuth, D. (2011). The Art of Computer Programming,
175 Vol 4, Addison Wesley
177 """
178 bits = self.n
179 start = None
180 if "start" in hints:
181 start = hints["start"]
182 elif "rank" in hints:
183 start = GrayCode.unrank(self.n, hints["rank"])
184 if start is not None:
185 self._current = start
186 current = self.current
187 graycode_bin = gray_to_bin(current)
188 if len(graycode_bin) > self.n:
189 raise ValueError('Gray code start has length %i but should '
190 'not be greater than %i' % (len(graycode_bin), bits))
191 self._current = int(current, 2)
192 graycode_int = int(''.join(graycode_bin), 2)
193 for i in range(graycode_int, 1 << bits):
194 if self._skip:
195 self._skip = False
196 else:
197 yield self.current
198 bbtc = (i ^ (i + 1))
199 gbtc = (bbtc ^ (bbtc >> 1))
200 self._current = (self._current ^ gbtc)
201 self._current = 0
203 def skip(self):
204 """
205 Skips the bit generation.
207 Examples
208 ========
210 >>> from sympy.combinatorics import GrayCode
211 >>> a = GrayCode(3)
212 >>> for i in a.generate_gray():
213 ... if i == '010':
214 ... a.skip()
215 ... print(i)
216 ...
217 000
218 001
219 011
220 010
221 111
222 101
223 100
225 See Also
226 ========
228 generate_gray
229 """
230 self._skip = True
232 @property
233 def rank(self):
234 """
235 Ranks the Gray code.
237 A ranking algorithm determines the position (or rank)
238 of a combinatorial object among all the objects w.r.t.
239 a given order. For example, the 4 bit binary reflected
240 Gray code (BRGC) '0101' has a rank of 6 as it appears in
241 the 6th position in the canonical ordering of the family
242 of 4 bit Gray codes.
244 Examples
245 ========
247 >>> from sympy.combinatorics import GrayCode
248 >>> a = GrayCode(3)
249 >>> list(a.generate_gray())
250 ['000', '001', '011', '010', '110', '111', '101', '100']
251 >>> GrayCode(3, start='100').rank
252 7
253 >>> GrayCode(3, rank=7).current
254 '100'
256 See Also
257 ========
259 unrank
261 References
262 ==========
264 .. [1] https://web.archive.org/web/20200224064753/http://statweb.stanford.edu/~susan/courses/s208/node12.html
266 """
267 if self._rank is None:
268 self._rank = int(gray_to_bin(self.current), 2)
269 return self._rank
271 @property
272 def current(self):
273 """
274 Returns the currently referenced Gray code as a bit string.
276 Examples
277 ========
279 >>> from sympy.combinatorics import GrayCode
280 >>> GrayCode(3, start='100').current
281 '100'
282 """
283 rv = self._current or '0'
284 if not isinstance(rv, str):
285 rv = bin(rv)[2:]
286 return rv.rjust(self.n, '0')
288 @classmethod
289 def unrank(self, n, rank):
290 """
291 Unranks an n-bit sized Gray code of rank k. This method exists
292 so that a derivative GrayCode class can define its own code of
293 a given rank.
295 The string here is generated in reverse order to allow for tail-call
296 optimization.
298 Examples
299 ========
301 >>> from sympy.combinatorics import GrayCode
302 >>> GrayCode(5, rank=3).current
303 '00010'
304 >>> GrayCode.unrank(5, 3)
305 '00010'
307 See Also
308 ========
310 rank
311 """
312 def _unrank(k, n):
313 if n == 1:
314 return str(k % 2)
315 m = 2**(n - 1)
316 if k < m:
317 return '0' + _unrank(k, n - 1)
318 return '1' + _unrank(m - (k % m) - 1, n - 1)
319 return _unrank(rank, n)
322def random_bitstring(n):
323 """
324 Generates a random bitlist of length n.
326 Examples
327 ========
329 >>> from sympy.combinatorics.graycode import random_bitstring
330 >>> random_bitstring(3) # doctest: +SKIP
331 100
332 """
333 return ''.join([random.choice('01') for i in range(n)])
336def gray_to_bin(bin_list):
337 """
338 Convert from Gray coding to binary coding.
340 We assume big endian encoding.
342 Examples
343 ========
345 >>> from sympy.combinatorics.graycode import gray_to_bin
346 >>> gray_to_bin('100')
347 '111'
349 See Also
350 ========
352 bin_to_gray
353 """
354 b = [bin_list[0]]
355 for i in range(1, len(bin_list)):
356 b += str(int(b[i - 1] != bin_list[i]))
357 return ''.join(b)
360def bin_to_gray(bin_list):
361 """
362 Convert from binary coding to gray coding.
364 We assume big endian encoding.
366 Examples
367 ========
369 >>> from sympy.combinatorics.graycode import bin_to_gray
370 >>> bin_to_gray('111')
371 '100'
373 See Also
374 ========
376 gray_to_bin
377 """
378 b = [bin_list[0]]
379 for i in range(1, len(bin_list)):
380 b += str(int(bin_list[i]) ^ int(bin_list[i - 1]))
381 return ''.join(b)
384def get_subset_from_bitstring(super_set, bitstring):
385 """
386 Gets the subset defined by the bitstring.
388 Examples
389 ========
391 >>> from sympy.combinatorics.graycode import get_subset_from_bitstring
392 >>> get_subset_from_bitstring(['a', 'b', 'c', 'd'], '0011')
393 ['c', 'd']
394 >>> get_subset_from_bitstring(['c', 'a', 'c', 'c'], '1100')
395 ['c', 'a']
397 See Also
398 ========
400 graycode_subsets
401 """
402 if len(super_set) != len(bitstring):
403 raise ValueError("The sizes of the lists are not equal")
404 return [super_set[i] for i, j in enumerate(bitstring)
405 if bitstring[i] == '1']
408def graycode_subsets(gray_code_set):
409 """
410 Generates the subsets as enumerated by a Gray code.
412 Examples
413 ========
415 >>> from sympy.combinatorics.graycode import graycode_subsets
416 >>> list(graycode_subsets(['a', 'b', 'c']))
417 [[], ['c'], ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'], \
418 ['a', 'c'], ['a']]
419 >>> list(graycode_subsets(['a', 'b', 'c', 'c']))
420 [[], ['c'], ['c', 'c'], ['c'], ['b', 'c'], ['b', 'c', 'c'], \
421 ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'c'], \
422 ['a', 'b', 'c'], ['a', 'c'], ['a', 'c', 'c'], ['a', 'c'], ['a']]
424 See Also
425 ========
427 get_subset_from_bitstring
428 """
429 for bitstring in list(GrayCode(len(gray_code_set)).generate_gray()):
430 yield get_subset_from_bitstring(gray_code_set, bitstring)