2

Today, I was thinking about random stuff like I sometimes do. I thought of an interesting question that I have no clue how to solve.

It started with me thinking about taking all 3 letter strings ("words"), and putting them through a profanity filter, just as a simple way to find out what words are filtered. Then, I realized that there was a (slightly, perhaps) more efficient way to write all letter combinations.

The traditional method would be:

aaa, aab, aac, aad, ... , zzz

But my idea was to allow the 3 letter combinations to be combined with each other. For example,

abcdef = abc, bcd, cde, and def

A reduction of 6 characters.

I wanted to know the shortest total character length required to represent every 3 letter word. I had no clue where to start, so I decided to simplify the problem to numbers (012345 represents 012, 123, 234, and 345): in other words, to represent 000 to 999 in as few digits as possible.

The only way that I can think to do this is to write code and have a computer brute force through every combination, but that would probably take years. Does anyone know anything about how to go about solving this?

[Clarification] In the last paragraph I mentioned brute forcing through every combination. I meant continuously adding digits until all 1000 numbers in the sequence, and doing that for every possible <3000 digit sequence (3000 is the longest that the sequence has to be: simply 000 to 999 in order) to find the shortest sequence that represents all 1000 numbers.

Ryoma
  • 23
  • 3 letter permutations (I assume add, dad are different for your case) are 26^3 = 17576. It will probably take the computer less than a millisecond to go through these. You may want to store all legitimate words are ~ 50k. Assuming average length of about 6 characters, less than 300KB of memory. In other words, this is a trivial problem for a computer to solve. – user625 Jun 18 '18 at 00:21
  • Kind of off-topic, but I've thought about this problem before w.r.t. a keypad in which one enters a four-digit numerical password. All that mattered for this keypad was that the $4$ digits were pressed in the correct order, regardless of what one typed before or after those $4$ digits. So, in the same vein you describe, typing "1234567" would test four different password possibilities. – Kaj Hansen Jun 18 '18 at 00:35
  • 1
    user625, I clarified my "brute forcing" in my question. I'm focusing more on the shortest way to represent all possible 3 character sequences, rather than the filter part that I began with. – Ryoma Jun 18 '18 at 00:47
  • @KajHansen, that is a great real world example of my question! I was pretty sure this had no practical meaning to doing it, and I am glad I was wrong. – Ryoma Jun 18 '18 at 00:49
  • Read about de Bruijn sequences: https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_graph – Ethan Bolker Jun 18 '18 at 00:50
  • @EthanBolker, thank you! I think this is exactly what I wanted. I had no clue how to put my question in Google-able terms instead of a long explanation of what I wanted to know. – Ryoma Jun 18 '18 at 00:54
  • I'm not sure if I know enough to solve this myself (I only recently graduated from high school), but I'll try! – Ryoma Jun 18 '18 at 00:57
  • I highly discourage using the term "permutation" to refer to anything other than an actual permutation. A permutation is most formally a bijective function from a finite set back to itself (most often the set ${1,2,3,\dots,n}$), but it can be interpreted as a sequence of letters or numbers but very specifically the sequence must contain every possible number or letter at least once from those available and must contain each no more than once. The objects you describe are instead better referred to as "strings." – JMoravitz Jun 18 '18 at 01:46
  • @Jmoravitz I was unsure whether "permutations" was correct when I posted, and I realized last night that 10P3 is only 720. Thanks for the new word. I've edited my post. – Ryoma Jun 18 '18 at 12:06

1 Answers1

1

De Bruijn sequences are indeed the answer. In fact there is an easy way of generating them.

If you restrict yourself to 3 symbols, you can take the alphabet $\{0,1,2\}$ which can be interpreted as the finite field (see wikipedia) $GF(3),$ where addition and multiplication is modulo 3.

Now there are sequences called maximal length sequences (see wikipedia here which discusses only $GF(2)$) over any field, and also over $GF(3),$ which are generated by recurrences corresponding to polynomials which are primitive. If you have a polynomial of degree $d,$ its roots have order $3^d-1$ and this polynomial generates the periodic maximal length sequence of length $3^d-1$. Within this sequence there is a unique position with $d-1$ consecutive zeroes.

Just insert an additional zero there and you get a DeBruijn sequence of length $3^d$ which represents every $d-$length pattern over $GF(3).$

You need to look for tables of primitive polynomials over $GF(3).$ See here

Example from that list:

Degree 4 10012

means (they display coefficients) the polynomial is

$$1*X^4+0*X^3+0*X^2+1*X+2*X^0$$

or $x^4+x^2+x-1$ mod 3, which corresponds to the recurrence

$$s[n-4]+s[n-2]+s[n-1]-s[n]=0 ~\pmod{3}$$

by taking multiplication by x as a shift operator, or equivalently

$$s[n]=s[n-1]+s[n-2]+s[n-4] \pmod{3}$$

as the generating recurrence. This recurrence, started with initial conditions (putting the zeroes here is convenient, followed by one nonzero entry)

$$s[0]=0,s[1]=0,s[2]=0,s[3]=1$$

will give a sequence $$(s[0],s[1],..,s[3^4-1])$$ of length 80. Just append a 0 in the beginning and you have your deBruijn sequence of length 81.

Edit: Smaller example

Degree 2 112

gives $X^2+X+2$ or $s[n-2]+s[n-1]+2s[n]=0,$ or $s[n]=s[n-1]+s[n-2] \pmod 3$

So start with $s[0]=0,s[1]=1$, get $s[2]=s[1]+s[0]=0+1=1$

$s[3]=1+1=2,$

$s[4]=1+2=0 \pmod 3,$

resulting in a sequence of length $3^2-1=8$ given by $$0,1,1,2,0,2,2,1;0,1,1,2,\ldots$$

Take one period and pre-pend a zero to get

$$0,0,1,1,2,0,2,2,1;0,1,\ldots$$ which spans the 9 possible states

$0,0\quad$ $0,1\quad$ $1,1\quad$ $1,2\quad$ $2,0\quad$ $0,2\quad$ $2,2\quad$ $2,1\quad$ $1,0$

kodlu
  • 9,338
  • Thank you for the answer! Because this is new to me, it will take a bit for me to fully comprehend this. I'll ask more questions if I get confused. Thanks again. – Ryoma Jun 18 '18 at 12:12
  • You're welcome, I'll put in a fully worked smaller example. – kodlu Jun 18 '18 at 12:25
  • Thanks for that. I think I might understand it a bit better now. – Ryoma Jun 18 '18 at 14:54