Reconstructing an ordering of a multiset from its consecutive submultisets 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.  
 A: (First, apologies to the administrators for not yet registering.)
If you consider S to be a debruijn sequence (a short sequence where each pair of letters from an alphabet occurs as a contiguous subword, e.g. 0120210), you will have a high amount of symmetry in the information given, and not be able to distinguish which sequence to reconstruct, even if you are told that it is a debruijn sequence.  (You might be able to if you were given a long enough initial segment of the sequence.)  Also, you may not be able to distinguish the string from its reverse, given only the information you list above.
So I think a unique reconstruction will be impossible.
I am looking at a similar problem where I want to compress a long list of numbers by looking at all sublists of length j for small j.  Here I have your information plus the ordering on all subsets of length j, but I have not found a way to reconstruct the
list because for each length (j-1) prefix, I have several choices to complete the length j list.  It seems I will need large j to do the reconstruction uniquely, which will defeat the intent of compressing the sequence.
Gerhard "Ask Me About System Design" Paseman, 2010.01.18
A: Generally speaking, I think these sequences should be non-reconstructible, at least when $j \leq r$.
For instance, consider the following two sequences:
01230123012301
01320132013201
These are indistinguishable (when j = 4) if we only look at the multisets and don't know the first few elements of the sequence. However, we can get around this problem for some fixed $p > 0$ by appending each of these sequences to some other sequence s.t. the initial fixed sequence has length $pt$. The only difference is that the first one has a consecutive subsequence of the form "x012" where the other one has one of the form "x013"; this can be remedied by appending an "x" to the end of both sequences.
A: No "palindromic sandwich" is reconstructible.  By this I mean an ordering of the form $aba'$ where $a'$ is $a$ reversed and $a$ is at least the length of the peek of the initial segment you get.  This ordering cannot be distinguished from $ab'a'$ regardless of the value of $j$; in other words, the problem cannot be solved when $p < \frac{1}{2}$.  Perhaps you want instead an algorithm that generates all possible orderings?
A: I don't think that any p<1 is large enough to work for all t. The hardest case to reconstruct is 2 distinct elements (if r>2, there is nothing to stop you from using only 2 of them or putting the rest once each in the front). Even if you have the first pt terms there are $2^{(1-p)t}$ ways to finish. There are only j+1 multisets of size j so the information you get back is just an ordered list of j+1 integers which add to t-j. These number about $\binom{t}{j}$ which is less that $t^j$ which will be outstripped by any exponential. But maybe I don't understand, what about sequences which are all 0 with a single 1 out past the initial part you are given (but at least j away from the end)? I don't think that even having the multiset of ordered j-substrings would be much help there. 
