deBruijnSequences 0.0.1

generate and decode binary debruin sequences of arbitrary length

A deBruijn sequence of span _n_ is a periodic sequence in which every possible
_n_-tuple over the alphabet occurs exactly once.

In this project, I created both a sequence generator and a decoder.

deBruijns can be in any base (that's why i used "alphabet" in the first sentence)
but I'm only interested in binary at the moment, so
most of this code assumes binary.

#### Papers
* Lempel 1992.pdf: Describes a method of construction of a deBruijn
sequence with an _n+1_ span from an _n_-span sequence. Also allows
such sequences to be efficiently decoded.
* Mitchell.pdf: Describes a method of construction of deBruijn sequences
that can then be decoded. Mitchell's construction builds _2n_-span sequences
from _n_-span sequences, and allows for recursive application and decoding to work with large dataset sizes.
* Patterson 1995.pdf
* The_Art_of_Computer_Programming - Vol 1.pdf
* tuliani2001.pdf
##### Generators
* Mitchell.py generates a sequence of span _2n_ from a sequence
span of _n_ . It's structured as a python iterator.
* KnuthAlgorithmR.py generates a sequence of span _n+1_ from a sequence
of span _n_ . It's structured as a python iterator.
* generate.py is an iterator that uses the above 2 iterators to generate a sequence of
any desired length. Import this file and call "iterbruijn(n)" to get a sequence of span _n_
* deBruijn.py is just a constant definition.
##### Scratch
This folder is where I'm putting old code experiments I don't want to
actually delete for whatever reason. Some of them worked until I broke them,
some never worked, some work but I don't like how they work.
### The Maths
A deBruijn is an infinite recurring sequence, but we usually just write down one round of the recurrence. Eg:
...0011001100110011... is a span 2 deBruijn, but we can really just write 0011 and remember that its effectively
circular. That also means we could write 1001, or 1100, or 0110. They're all the same, effectively.<p>
I like to call a span-v deBruijn D_v. Its much simpler than "Span-v deBruijn sequence". The length
of D_v is always going to be 2^v<p>
We'll need to remember the location of the all-0-tuple and all-1-tuple for decoding purposes later.
These are called s and s^' respectively.

[MitchellEtAl1996] talks about modifications to deBruijns:
###### Punctured deBruijn
If you take D_v, find the v-tuple of all zeroes, and then remove one 0 from there,
you're left with a sequence that has **almost** all possible v-tuples, called a punctured deBruijn. Let's call
this D^'_v
###### Double-Punctured deBruijn
If you take a punctured deBruijn, find the v-tuple of all ones, and remove one 1 from there, you're left
with a double-punctured deBruijn sequence. Let's call this D^''_v
###### Enhanced deBruijn
[MitchellEtAl1996] never names but uses a sequence that rather than having a 0 and 1 removed as in
a double-punctured deBruijn, **adds** a 0 and a 1. This yields a sequence that has all possible tuples,
but the all-zero and all-one tuples are in there twice. I call these "enhanced" deBruijns, but I write
it as D⁺_v
###### [MitchellEtAl1996] Construction
Its actually pretty straight-forward. Start with a known D_v. Create A=D^''_v,
and B=D⁺_v. If the length of D_v is n, then length of A is n-2,
and the length of B is n+2. If you concatenate 1+n/2 copies of A, you'll get a sequence of the same
length as n/2 -1 concatenated copies of B. <p> The construction method is:
1. interleave these two sequences B and A, creating a sequence 2²ⁿ-4 long.
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
important value we need to remember. It's called T.
You're now left with D^''_2v. From here, you can trivially generate D_2v
as well as D⁺_2v. With those, you can do another iteration and create D_4v, etc.
###### [MitchellEtAl1996] Decoding
The algorithm as described by [MitchellEtAl1996] works only with double-punctured deBruijns constructed using
the above algorithm. Decoding looks convoluted, but is actually straight-forward. D^''_2n
was 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
A or B, and the odd bits to the other. Since there are several copies each of A and B in
D^''_2n, we end up with 2 simultaneous equations we need to solve. 2 equations, 1 unknown,
so it's not terribly hard to solve. There are several ways to map the even bits of x to A or B:
1. If the even bits are all 0 or all 1, then the even bits must map to B.
1. if the odd bits are all 0 or all 1, then the odd bits must map to B.
1. if both the even bits tuple and the odd bits tuple are at an even position within A, then the position
of x must be even, and the odd bits tuple maps to A.
1. if both the even bits tuple and the odd bits tuple are at an odd position within A, then the position
of x must be even, and the odd bits tuple maps to A.
1. if the even bits tuple and odd bits tuple are of different parity, then the position of x must be odd,
and the odd bits tuple maps to B.

The above can be a little hard to follow. It certainly took me a few weeks to internalize. I found that
working through the construction and decoding methods on paper starting with D₃ helped a lot.
I'd welcome efforts to restate the above to make it easier to follow.


##### Using the Code
At the moment, the code is asymmetric: it can generate deBruijns of any span greater than 2, but
it cannot decode odd-sized deBruijns at all, and for even deBruijns, it actually works against
double-punctured deBruijns with a span of 6 or larger, not a simple deBruijn... I consider these limits
bugs which I'm working around, for the moment.

###### To generate a deBruijn of any length:
```python
import generate
deBruijn_of_span_v = [y for y in generate.iterbruijn(v)]

```

###### To generate a double-punctured deBruijn suitable for decoding:
```python
import generate
double_punctured_deBruijn_of_span_v = [y for y in generate.iterdpdB(v)]

```


###### To decode:
```python
import MitchellDecode
position_of_x = MitchellDecode.MitchellDecode(x)

```

##### setup for using mouseImageFetch
you'll need to be able to connect to the mouse. you can either be root, or do the following:
<p>(from https://stackoverflow.com/a/31994168)
create a file in /etc/udev/rules.d, mine is named 50-RichardWazHeer.rules<p>
in it, put something like:<p>
ACTION=="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'"

sudo udevadm control --reload
sudo udevadm trigger

unplug and replug your mouse.