2 ms·
Is there, for a given k, an easy to remember sequence (easy to remember algorithm with little state) that has all the k-grams with the same frequency? For k=1:
by js8 10y ago
Is there, for a given k, an easy to remember sequence (easy to remember algorithm with little state) that has all the k-grams with the same frequency?
For k=1: 01 repeating
For k=2: 0011 repeating
For k=3: 00010111 repeating
- justinpombrio 10y agoThey're called De Bruijn sequences[1], and there's an algorithm for constructing them. I'm not sure how easy it is to run in your head, though. [1] https://en.wikipedia.org/wiki/De_Bruijn_sequence#Algorithm https://en.wikipedia.org/wiki/De_Bruijn_sequence#Algorithm
- WillKirkby 10y agoprobably relevant: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence edit: dangit, beaten to the punch.