We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ and $r$ and, for some fixed positive integer $j$, the set of multisets $\{ s_k, s_{k+1}, ... s_{k+j-1} \}$ for $1 \le k \le t-j+1$. (Note that we are not given either the order of elements in each multiset or the order of the multisets.) We also know $s_1, ... s_{\lfloor pt \rfloor}$ for some fixed $0 < p < 1$.
For what values of $t, r, j, p$ is it possible to reconstruct the entire ordering $s_1, ... s_t$? For those values, what is the average- or worst-case complexity of doing so?
Edit (Qiaochu Yuan): Here's a restatement of the problem in the language Steve Huntsman is using. The generalized de Brujin graph $B(r, j)$ (it does not seem to have a standard name) has vertices the set of all words of length $j$ from an alphabet of size $r$ and edges defined as follows: the word $w_1, ... w_j$ has an edge directed to the word $w_2 ... w_j w_{j+1}$ for all possible choices of $w_{j+1}$. There is a natural equivalence relation on words where two words are equivalent if the same letters occur in them with the same frequency. What we are trying to do is reconstruct a walk on $B(r, j)$ of length $t - j + 1$ given only the set of equivalence classes of its vertices, and also given an initial segment of the walk which is some fixed proportion of the entire walk.
