\nI like to call a span-v deBruijn Dv. Its much simpler than \"Span-v deBruijn sequence\". The length\nof Dv is always going to be 2v
\nWe'll need to remember the location of the all-0-tuple and all-1-tuple for decoding purposes later.\nThese are called s and s' respectively.\n\n[MitchellEtAl1996] talks about modifications to deBruijns:\n###### Punctured deBruijn\nIf you take Dv, find the v-tuple of all zeroes, and then remove one 0 from there, \nyou're left with a sequence that has **almost** all possible v-tuples, called a punctured deBruijn. Let's call\nthis D'v\n###### Double-Punctured deBruijn\nIf you take a punctured deBruijn, find the v-tuple of all ones, and remove one 1 from there, you're left\nwith a double-punctured deBruijn sequence. Let's call this D''v\n###### Enhanced deBruijn\n[MitchellEtAl1996] never names but uses a sequence that rather than having a 0 and 1 removed as in \na double-punctured deBruijn, **adds** a 0 and a 1. This yields a sequence that has all possible tuples,\nbut the all-zero and all-one tuples are in there twice. I call these \"enhanced\" deBruijns, but I write \nit as D+v\n###### [MitchellEtAl1996] Construction\nIts actually pretty straight-forward. Start with a known Dv. Create A=D''v,\nand B=D+v. If the length of Dv is n, then length of A is n-2, \nand the length of B is n+2. If you concatenate 1+n/2 copies of A, you'll get a sequence of the same \nlength as n/2 -1 concatenated copies of B.
The construction method is:\n 1. interleave these two sequences B and A, creating a sequence 22n-4 long.\n 2. find the v-2 tuple (1,0,1,0,...) and insert (1,0). The location of the (1,0,1,0...) v-tuple is another\n important value we need to remember. It's called T.\nYou're now left with D''2v. From here, you can trivially generate D2v \nas well as D+2v. With those, you can do another iteration and create D4v, etc.\n###### [MitchellEtAl1996] Decoding\nThe algorithm as described by [MitchellEtAl1996] works only with double-punctured deBruijns constructed using\nthe above algorithm. Decoding looks convoluted, but is actually straight-forward. D''2n\nwas built from 2 sequences A and B. If x is a 2n-tuple to be decoded, you decode by mapping even bits of x to one of\nA or B, and the odd bits to the other. Since there are several copies each of A and B in\nD''2n, we end up with 2 simultaneous equations we need to solve. 2 equations, 1 unknown,\nso it's not terribly hard to solve. There are several ways to map the even bits of x to A or B:\n1. If the even bits are all 0 or all 1, then the even bits must map to B.\n1. if the odd bits are all 0 or all 1, then the odd bits must map to B.\n1. if both the even bits tuple and the odd bits tuple are at an even position within A, then the position\nof x must be even, and the odd bits tuple maps to A.\n1. if both the even bits tuple and the odd bits tuple are at an odd position within A, then the position\nof x must be even, and the odd bits tuple maps to A. \n1. if the even bits tuple and odd bits tuple are of different parity, then the position of x must be odd,\nand the odd bits tuple maps to B.\n\nThe above can be a little hard to follow. It certainly took me a few weeks to internalize. I found that\nworking through the construction and decoding methods on paper starting with D3 helped a lot.\nI'd welcome efforts to restate the above to make it easier to follow. \n\n\n##### Using the Code\nAt the moment, the code is asymmetric: it can generate deBruijns of any span greater than 2, but \nit cannot decode odd-sized deBruijns at all, and for even deBruijns, it actually works against \ndouble-punctured deBruijns with a span of 6 or larger, not a simple deBruijn... I consider these limits\nbugs which I'm working around, for the moment.\n\n###### To generate a deBruijn of any length:\n```python\nimport generate\ndeBruijn_of_span_v = [y for y in generate.iterbruijn(v)]\n\n```\n\n###### To generate a double-punctured deBruijn suitable for decoding:\n```python\nimport generate\ndouble_punctured_deBruijn_of_span_v = [y for y in generate.iterdpdB(v)]\n\n```\n\n\n###### To decode:\n```python\nimport MitchellDecode\nposition_of_x = MitchellDecode.MitchellDecode(x)\n\n```\n\n##### setup for using mouseImageFetch\nyou'll need to be able to connect to the mouse. you can either be root, or do the following:\n
(from https://stackoverflow.com/a/31994168)\ncreate a file in /etc/udev/rules.d, mine is named 50-RichardWazHeer.rules
\nin it, put something like:
\nACTION==\"add\", SUBSYSTEMS==\"usb\", ATTRS{idVendor}==\"04f3\", ATTRS{idProduct}==\"0235\", MODE=\"666\", GROUP=\"richard\", PROGRAM=\"/bin/sh -c 'echo -n $id:1.0 >/sys/bus/usb/drivers/usbhid/unbind'\"\n \nsudo udevadm control --reload\nsudo udevadm trigger\n\nunplug and replug your mouse.", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/emteeoh/deBruijn-Sequences", "keywords": "", "license": "AGPL", "maintainer": "", "maintainer_email": "", "name": "deBruijnSequences", "package_url": "https://pypi.org/project/deBruijnSequences/", "platform": "", "project_url": "https://pypi.org/project/deBruijnSequences/", "project_urls": { "Homepage": "https://github.com/emteeoh/deBruijn-Sequences" }, "release_url": "https://pypi.org/project/deBruijnSequences/0.0.1/", "requires_dist": null, "requires_python": "", "summary": "generate and decode binary debruin sequences of arbitrary length", "version": "0.0.1" }, "last_serial": 4181747, "releases": { "0.0.1": [ { "comment_text": "", "digests": { "md5": "3866575dd5928d359ea2de4beb535570", "sha256": "f33da7d0e05b0bf07c6588e41d3df90c63476efa3c9dd28408a05c285dd117e5" }, "downloads": -1, "filename": "deBruijnSequences-0.0.1.tar.gz", "has_sig": false, "md5_digest": "3866575dd5928d359ea2de4beb535570", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5257, "upload_time": "2018-08-17T20:58:11", "url": "https://files.pythonhosted.org/packages/9c/40/f555a4df3f3e0a2304514a82a2b42fdf8911d6a86ae0c960325593fa63fe/deBruijnSequences-0.0.1.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "3866575dd5928d359ea2de4beb535570", "sha256": "f33da7d0e05b0bf07c6588e41d3df90c63476efa3c9dd28408a05c285dd117e5" }, "downloads": -1, "filename": "deBruijnSequences-0.0.1.tar.gz", "has_sig": false, "md5_digest": "3866575dd5928d359ea2de4beb535570", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 5257, "upload_time": "2018-08-17T20:58:11", "url": "https://files.pythonhosted.org/packages/9c/40/f555a4df3f3e0a2304514a82a2b42fdf8911d6a86ae0c960325593fa63fe/deBruijnSequences-0.0.1.tar.gz" } ] }