CODEWITHSUNDEEP
state-machine
Malteaser6900
Malteaser6900

Reputation: 73

State Machine Capable of All Transitions

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.

State Transitions for 5 States

Any ideas on how to approach this please?

Upvotes: 0

Views: 222

Answers (1)

J. P. Petersen
J. P. Petersen

Reputation: 5031

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]

Upvotes: 1

Related Questions