The data consists of a graph whose vertices correspond to the output sequence you desire and where there is an edge (with probability 1) from string x to string y if and only if x precedes y.

This model will arise from the desired sequence as a single training example (learning the probability of each pair of consecutive tokens), provided none are repeated.

Now run your Markov chain with initial input {first token in your sequence}.