State Machine Capable of All Transitions

Question

I am trying to design a state machine which will traverse all possible transitions between states. However, the state machine cannot move from a given state back to itself. From the diagram below, I have worked out that given the number of states (N), the number of transitions is equal to N^2 - N.

Any ideas on how to approach this please?

Yes, I have a 5 bit pattern that I want to send to a device will all possible transitions ie. 32 states with 992 transitions — Malteaser6900
Example: For a 2 bit pattern I have 4 states A,B,C,D. I want to cover A>B, A>C, A>D, B>A, B>C, B>D, C>A, C>B, C>D, D>A, D>B and D>C. — Malteaser6900
Can't you iterate over all current states and next states, and just discard those where they are equal? — J. P. Petersen

J. P. Petersen J. P. Petersen · Accepted Answer · 2017-01-11T14:44:05

After having misunderstood the problem the first time, here is another attempt.

So we want to transverse the graph in one go, and we are not allowed to use the same transition twice. The trick is probably to leave a track free to get back to the starting state.

states = 4  # Select number of states

path = [0]  # Start in state 0 (must be zero)

def walk(path):
   home_state = path[-1]
   for i in range(home_state + 2, states):
       # We leave a state out that we go to next
       path.append(i)
       path.append(home_state)
   if home_state + 1 < states:
       path.append(home_state + 1)
       walk(path)
       path.append(home_state)

walk(path)
print path

should give

[0, 2, 0, 3, 0, 1, 3, 1, 2, 3, 2, 1, 0]

State Machine Capable of All Transitions

1 Answers