My question concerns the average-case/worst-case computational complexity of the following task:

We have a hidden ordered set $S$ with some number of distinct elements $R$, $[0, 1, ..., R]$ $\in$ $S$ (which we represent using integers), where cardinality $|S|=T$. For the $R=2$ case, $S$ can represented as a length $T$ binary string, for $R=3$ case $S$ can be represented as a numerical string in base 3 (i.e. '011122211000120002222...10210002'$), and so forth.

Our challenge is to recover the ordered set $S$ using only the following information:

1. The cardinality $|S|=T$.

2. The number of distinct elements $R$, $[0, 1, ..., R]$ $\in$ $S$.

3. All possible fixed-cardinality subsets $[s_1,s_2,...,s_{(T-J)}]$ $\subset$ $S$ (which may be non-disjoint), where $J = |s_k|$ is the cardinality of each subset. However, the catch is that the ordering in $S$ is not preserved, i.e. that the elements in each $s_k$ are scrambled. For the previous binary string example, this is equivalent to trying to recover the full string given access to only the number of 1's and 0's for all consecutive subsequences of length $J$.

4. The ordering of $S$ may be conspiratorially set up to have a large number of 'degenerate' subsets $s_k$ with identical counts of each element. However, we still know exactly how many copies of each subset are present.

Intuitively, I feel like there will be an exponential penalty for reconstructing $S$ which depends strongly on the number of 'degenerate' subsets from (4). However, this is the sort of problem where I can imagine there might be (perhaps unexpected) nice average-case algorithms.

Maybe this is helpful... for the $R=2$ case one can consider the undirected graph, $G(V,E)$, where:

1. G(V,E) consists of a linear array of $N$ vertices $[v_1, ..., v_k, ..., v_N]$ $\in$ $V(G)$, where each vertex between $v_1$ and $v_N$ is connected (i.e. has edges from the set $[e_1, ..., e_j, ..., e_M]$ $\in$ $V(E)$) between itself and its two nearest neighbors at positions $(k-1)$ and $(k+1)$. (At $v_1$ and $v_N$ there is only a single nearest neighbor connection to $v_2$ and $v_{N-1}$, respectively.)

2. Each $v_k$ $\in$ $G(V)$ has is a single circular connection/edge back to itself.

Now, to solve an equivalent problem to finding the hidden ordered set $S$, we use the element counts of the scrambled subsets $[s_1,s_2,...,s_{(T-J)}]$ $\subset$ $S$ to help guide a length $|S|=T$ tour through $G(V,E)$ where:

1. Though there are no restrictions for traveling along connections/edges, for tours through the graph, each vertex may only be visited a total of $c_k$ times, where there is a specified value - $[c_1, ..., c_k, ..., c_N]$ - for each $v_k$ $\in$ $V(G)$. Let $\sum_{k=1}^{N}c_k$ = $T$, i.e. the cardinality of the ordered set $S$ in the earlier problem description. (One should be able to fairly easily create a more complex graph with $\sum_{k=1}^{N}c_k$ vertices and appropriately mapped edges, but hopefully the above description is easier to conceptualize.)

2. The decision to move along a particular edge is constrained by the edge one had chosen to travel along $J$ moves earlier (where $J$ is the cardinality of the scrambled subsets $[s_1,s_2,...,s_{(T-J)}]$ $\subset$ $S$). In particular, if you had moved to the $(k+1)th$ vertex $J$ moves earlier, you must either travel along the circular edge (back to your starting vertex) or to the current $(k-1)th$ vertex. Alternatively, if you had moved to the $(k-1)th$ vertex $J$ moves earlier, you must either move along the circular edge or to the current $(k+1)th$ vertex.

Here, $G(V,E)$ is just being set up to imagine the process of trying to order all of the scrambled subsets $[s_1,s_2,...,s_{(T-J)}]$ $\subset$ $S$ so that each each successive subset has one more or one less of a single element (i.e. in the binary-string $R=2$, $J=100$ example, a subset reporting 50 1's and 50 0's might be placed adjacent to one reporting 51 1's and 49 0's).

Moving to the $(k+1)th$ vertex is made equivalent to having one more '1' and losing a '0' moving from one subset to the next (hypothesized to be adjacent in ordered $S$), moving the $(k-1)th$ vertex is equivalent to having one more '0' and losing a '1', and traveling along the circular connection/edge means losing and gaining a '1' or a '0'.

However, there is a lag of $|s_k|=J$ moves before we begin to 'test' that a given ordering is acceptable (and the test should be easily passable in a probabilistic sense early on with large $c_k$ for each vertex). Even provided the first $J$ moves, the number of possible paths to check before a unique length $|S|=T$ tour can be found would appear to scale exponentially as a function of the number of 'degenerate' $s_k$ with identical counts for 1's and 0's.