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?