General Question

PhiNotPi's avatar

Is there a way to order the letters A, B, and C so that every possible trigraph appears once? (see details)

Asked by PhiNotPi (12677points) October 19th, 2011

If you have a simple alphabet (for now, just three letters), is there a way to create a list of letters so that every possible trigraph (group of three letters) appears once and only once? Assume that the list loops around, so the last letters connect to the first letters.

An example for an alphabet of size two is “AABBBABA”. Here, you can see that every possible trigraph (aaa, aab, aba, abb, etc.) is located in the string. The AAA is formed by the last letter being connected to the first two.

How would this be done with an alphabet of size n=3? If it helps, any solution would have to have a length of n^3, and there needs to an equal number of each letter in the string. There are going to be many solutions, but I only want one.

So, is it possible to do this with an alphabet of any size? Is there an algorithm to solve this problem?

This is NOT homework.

Observing members: 0 Composing members: 0

6 Answers

PhiNotPi's avatar

@cazzie Is there a specific place to look on that site? A link to a massive mathematical site is very vague. That same response applies to almost every math problem I have asked here.

PhiNotPi's avatar

@linguaphile The pattern ABC does not appear in that string, along with three other trigraphs..

6rant6's avatar

So the size of the ring grows exponentially? n^3

I wonder if there is a way to come up with an infeasible solution and then move toward a feasible one, algorithmically? Or perhaps some kind of tree?

6rant6's avatar

I can describe an algorithm to generate a solution if there is one. But testing above n=6 or so is going to be a bitch.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther