Spaces:
Sleeping
Sleeping
| from sympy.core import Basic, Integer | |
| import random | |
| class GrayCode(Basic): | |
| """ | |
| A Gray code is essentially a Hamiltonian walk on | |
| a n-dimensional cube with edge length of one. | |
| The vertices of the cube are represented by vectors | |
| whose values are binary. The Hamilton walk visits | |
| each vertex exactly once. The Gray code for a 3d | |
| cube is ['000','100','110','010','011','111','101', | |
| '001']. | |
| A Gray code solves the problem of sequentially | |
| generating all possible subsets of n objects in such | |
| a way that each subset is obtained from the previous | |
| one by either deleting or adding a single object. | |
| In the above example, 1 indicates that the object is | |
| present, and 0 indicates that its absent. | |
| Gray codes have applications in statistics as well when | |
| we want to compute various statistics related to subsets | |
| in an efficient manner. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> list(a.generate_gray()) | |
| ['000', '001', '011', '010', '110', '111', '101', '100'] | |
| >>> a = GrayCode(4) | |
| >>> list(a.generate_gray()) | |
| ['0000', '0001', '0011', '0010', '0110', '0111', '0101', '0100', \ | |
| '1100', '1101', '1111', '1110', '1010', '1011', '1001', '1000'] | |
| References | |
| ========== | |
| .. [1] Nijenhuis,A. and Wilf,H.S.(1978). | |
| Combinatorial Algorithms. Academic Press. | |
| .. [2] Knuth, D. (2011). The Art of Computer Programming, Vol 4 | |
| Addison Wesley | |
| """ | |
| _skip = False | |
| _current = 0 | |
| _rank = None | |
| def __new__(cls, n, *args, **kw_args): | |
| """ | |
| Default constructor. | |
| It takes a single argument ``n`` which gives the dimension of the Gray | |
| code. The starting Gray code string (``start``) or the starting ``rank`` | |
| may also be given; the default is to start at rank = 0 ('0...0'). | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> a | |
| GrayCode(3) | |
| >>> a.n | |
| 3 | |
| >>> a = GrayCode(3, start='100') | |
| >>> a.current | |
| '100' | |
| >>> a = GrayCode(4, rank=4) | |
| >>> a.current | |
| '0110' | |
| >>> a.rank | |
| 4 | |
| """ | |
| if n < 1 or int(n) != n: | |
| raise ValueError( | |
| 'Gray code dimension must be a positive integer, not %i' % n) | |
| n = Integer(n) | |
| args = (n,) + args | |
| obj = Basic.__new__(cls, *args) | |
| if 'start' in kw_args: | |
| obj._current = kw_args["start"] | |
| if len(obj._current) > n: | |
| raise ValueError('Gray code start has length %i but ' | |
| 'should not be greater than %i' % (len(obj._current), n)) | |
| elif 'rank' in kw_args: | |
| if int(kw_args["rank"]) != kw_args["rank"]: | |
| raise ValueError('Gray code rank must be a positive integer, ' | |
| 'not %i' % kw_args["rank"]) | |
| obj._rank = int(kw_args["rank"]) % obj.selections | |
| obj._current = obj.unrank(n, obj._rank) | |
| return obj | |
| def next(self, delta=1): | |
| """ | |
| Returns the Gray code a distance ``delta`` (default = 1) from the | |
| current value in canonical order. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3, start='110') | |
| >>> a.next().current | |
| '111' | |
| >>> a.next(-1).current | |
| '010' | |
| """ | |
| return GrayCode(self.n, rank=(self.rank + delta) % self.selections) | |
| def selections(self): | |
| """ | |
| Returns the number of bit vectors in the Gray code. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> a.selections | |
| 8 | |
| """ | |
| return 2**self.n | |
| def n(self): | |
| """ | |
| Returns the dimension of the Gray code. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(5) | |
| >>> a.n | |
| 5 | |
| """ | |
| return self.args[0] | |
| def generate_gray(self, **hints): | |
| """ | |
| Generates the sequence of bit vectors of a Gray Code. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> list(a.generate_gray()) | |
| ['000', '001', '011', '010', '110', '111', '101', '100'] | |
| >>> list(a.generate_gray(start='011')) | |
| ['011', '010', '110', '111', '101', '100'] | |
| >>> list(a.generate_gray(rank=4)) | |
| ['110', '111', '101', '100'] | |
| See Also | |
| ======== | |
| skip | |
| References | |
| ========== | |
| .. [1] Knuth, D. (2011). The Art of Computer Programming, | |
| Vol 4, Addison Wesley | |
| """ | |
| bits = self.n | |
| start = None | |
| if "start" in hints: | |
| start = hints["start"] | |
| elif "rank" in hints: | |
| start = GrayCode.unrank(self.n, hints["rank"]) | |
| if start is not None: | |
| self._current = start | |
| current = self.current | |
| graycode_bin = gray_to_bin(current) | |
| if len(graycode_bin) > self.n: | |
| raise ValueError('Gray code start has length %i but should ' | |
| 'not be greater than %i' % (len(graycode_bin), bits)) | |
| self._current = int(current, 2) | |
| graycode_int = int(''.join(graycode_bin), 2) | |
| for i in range(graycode_int, 1 << bits): | |
| if self._skip: | |
| self._skip = False | |
| else: | |
| yield self.current | |
| bbtc = (i ^ (i + 1)) | |
| gbtc = (bbtc ^ (bbtc >> 1)) | |
| self._current = (self._current ^ gbtc) | |
| self._current = 0 | |
| def skip(self): | |
| """ | |
| Skips the bit generation. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> for i in a.generate_gray(): | |
| ... if i == '010': | |
| ... a.skip() | |
| ... print(i) | |
| ... | |
| 000 | |
| 001 | |
| 011 | |
| 010 | |
| 111 | |
| 101 | |
| 100 | |
| See Also | |
| ======== | |
| generate_gray | |
| """ | |
| self._skip = True | |
| def rank(self): | |
| """ | |
| Ranks the Gray code. | |
| A ranking algorithm determines the position (or rank) | |
| of a combinatorial object among all the objects w.r.t. | |
| a given order. For example, the 4 bit binary reflected | |
| Gray code (BRGC) '0101' has a rank of 6 as it appears in | |
| the 6th position in the canonical ordering of the family | |
| of 4 bit Gray codes. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> a = GrayCode(3) | |
| >>> list(a.generate_gray()) | |
| ['000', '001', '011', '010', '110', '111', '101', '100'] | |
| >>> GrayCode(3, start='100').rank | |
| 7 | |
| >>> GrayCode(3, rank=7).current | |
| '100' | |
| See Also | |
| ======== | |
| unrank | |
| References | |
| ========== | |
| .. [1] https://web.archive.org/web/20200224064753/http://statweb.stanford.edu/~susan/courses/s208/node12.html | |
| """ | |
| if self._rank is None: | |
| self._rank = int(gray_to_bin(self.current), 2) | |
| return self._rank | |
| def current(self): | |
| """ | |
| Returns the currently referenced Gray code as a bit string. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> GrayCode(3, start='100').current | |
| '100' | |
| """ | |
| rv = self._current or '0' | |
| if not isinstance(rv, str): | |
| rv = bin(rv)[2:] | |
| return rv.rjust(self.n, '0') | |
| def unrank(self, n, rank): | |
| """ | |
| Unranks an n-bit sized Gray code of rank k. This method exists | |
| so that a derivative GrayCode class can define its own code of | |
| a given rank. | |
| The string here is generated in reverse order to allow for tail-call | |
| optimization. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics import GrayCode | |
| >>> GrayCode(5, rank=3).current | |
| '00010' | |
| >>> GrayCode.unrank(5, 3) | |
| '00010' | |
| See Also | |
| ======== | |
| rank | |
| """ | |
| def _unrank(k, n): | |
| if n == 1: | |
| return str(k % 2) | |
| m = 2**(n - 1) | |
| if k < m: | |
| return '0' + _unrank(k, n - 1) | |
| return '1' + _unrank(m - (k % m) - 1, n - 1) | |
| return _unrank(rank, n) | |
| def random_bitstring(n): | |
| """ | |
| Generates a random bitlist of length n. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.graycode import random_bitstring | |
| >>> random_bitstring(3) # doctest: +SKIP | |
| 100 | |
| """ | |
| return ''.join([random.choice('01') for i in range(n)]) | |
| def gray_to_bin(bin_list): | |
| """ | |
| Convert from Gray coding to binary coding. | |
| We assume big endian encoding. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.graycode import gray_to_bin | |
| >>> gray_to_bin('100') | |
| '111' | |
| See Also | |
| ======== | |
| bin_to_gray | |
| """ | |
| b = [bin_list[0]] | |
| for i in range(1, len(bin_list)): | |
| b += str(int(b[i - 1] != bin_list[i])) | |
| return ''.join(b) | |
| def bin_to_gray(bin_list): | |
| """ | |
| Convert from binary coding to gray coding. | |
| We assume big endian encoding. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.graycode import bin_to_gray | |
| >>> bin_to_gray('111') | |
| '100' | |
| See Also | |
| ======== | |
| gray_to_bin | |
| """ | |
| b = [bin_list[0]] | |
| for i in range(1, len(bin_list)): | |
| b += str(int(bin_list[i]) ^ int(bin_list[i - 1])) | |
| return ''.join(b) | |
| def get_subset_from_bitstring(super_set, bitstring): | |
| """ | |
| Gets the subset defined by the bitstring. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.graycode import get_subset_from_bitstring | |
| >>> get_subset_from_bitstring(['a', 'b', 'c', 'd'], '0011') | |
| ['c', 'd'] | |
| >>> get_subset_from_bitstring(['c', 'a', 'c', 'c'], '1100') | |
| ['c', 'a'] | |
| See Also | |
| ======== | |
| graycode_subsets | |
| """ | |
| if len(super_set) != len(bitstring): | |
| raise ValueError("The sizes of the lists are not equal") | |
| return [super_set[i] for i, j in enumerate(bitstring) | |
| if bitstring[i] == '1'] | |
| def graycode_subsets(gray_code_set): | |
| """ | |
| Generates the subsets as enumerated by a Gray code. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.graycode import graycode_subsets | |
| >>> list(graycode_subsets(['a', 'b', 'c'])) | |
| [[], ['c'], ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'], \ | |
| ['a', 'c'], ['a']] | |
| >>> list(graycode_subsets(['a', 'b', 'c', 'c'])) | |
| [[], ['c'], ['c', 'c'], ['c'], ['b', 'c'], ['b', 'c', 'c'], \ | |
| ['b', 'c'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'c'], \ | |
| ['a', 'b', 'c'], ['a', 'c'], ['a', 'c', 'c'], ['a', 'c'], ['a']] | |
| See Also | |
| ======== | |
| get_subset_from_bitstring | |
| """ | |
| for bitstring in list(GrayCode(len(gray_code_set)).generate_gray()): | |
| yield get_subset_from_bitstring(gray_code_set, bitstring) | |