Given a list of (absolute valued) pair differences ordered and with duplicates removed, how can we recover/reconstruct the list that generated these differences? We do not know anything about the generating list, not the individual values and not its length.
Normally, the objective is to find the shortest possible generating list, but also to find all solutions.
Here is an example: Given the (absolute valued) difference list of $$[1,6,7,8,12,13,14,15,19,20,21,26,27,33,34]$$ we find the following solutions, i.e. lists that could have generated these pair differences:
$[1,2,9,16,22,28,35],[1,8,14,20,27,34,35],[1,2,8,16,22,28,35],[1,8,14,20,28,34,35]$
These solutions are "normalized" in that they always start with $1$ and end with $1+\max(\text{difference list})$.
The difference list was actually generated by the list $[5,12,18,24,31,32,38,39]$. It is "normalized" (all numbers are subtracted by some constant integer) to $[1,8,14,20,27,28,34,35]$ which happens to be one of the found solutions.
I have thought about this for some days now and written:
a Picat (constraint programming) model with some experiments. The model also handles cases where there are duplicates in the difference lists.
a MiniZinc model implementing the base version. Here is a MiniZinc-Python program for experimenting with the MiniZinc model.
a draft describing the problem and some experiments/findings/invariants. Unfortunately, right now it's not as "formal" as I would want it.
The base model that is described below has been implemented in the Picat model (link above). The description uses constraint programming parlance.
"origin" list (generator): This "origin" list is not really in the model but it is essential to understand the model. The "origin" is the list that generates the list of pair differences that is the input of the model. The origin list is not known by the model and we don't know either its length or any of its elements (integers).
The objective of the model is to find out what this origin list is, or rather some variant of it since in real use we don't know what the origin list is.
Let us call this origin list
L
with lengthLen
. Then the difference list is calculated as follows:Get all the pair differences of
L
:L2 = [abs([L[I]-L[J]) : I in 1..Len, J in I+1..Len]
Sorting the pair difference list
L2
and removing the duplicates give the sorted difference list:Diffs = L2.sort_remove_dups
.
Note: This part is used in the model just to generate difference lists to test. The input to the model is the difference list.
"normalization" of the origin: Each origin list can be normalized to a list which starts with $1$. Let
L2
be the sorted version ofL
and with lengthLLen
. Then the normalized version is[L2[I] - L2[1] + 1 : I in 1..LLen]
, i.e. subtract all integers in the listL2
with the first value of the list and add $1$ (the start value of the normalized list).Note: Instead of $1$ as the start value, we could use $0$ instead (or any other value), but I tend to prefer that the list start with $1$.
The concept of normalization is important since the solution of the model can be seen as a normalized version of the origin.
The input of the model is
diffs
: The difference list that is generated by the (unknown) origin list as described above: it is an ordered list of distinct integers. It has lengthlen
and a maximum value (the last value)max_val
.
The model:
The model loops through a value of lengths of the solution list, starting with min_len
:
min_len
: The minimum length of a possible solution. This value is calculated as $$\min\_\text{len}=\left\lfloor1+\frac{\sqrt{1+8\cdot\text{len}}}2\right\rfloor.$$ The formula is based on the calculation of the number of difference pairs in a given list of length $n$, which is given by $n(n-1)/2$. Thus, given the length of the difference list (len
), the minimum length ismin_len
.For finding one of the shortest solutions, we loop over the the possible lengths (
n
) of the solution list, from the minimum lengthmin_len
to some (arbitrary) upper length.Note: I have not found a way of calculating this upper value given the inputs of the model. The upper value of the length of the solution is actually the length of the origin list, but in the model we don't know anything about the origin list.
Note 2: In most cases, the length of the solution is
min_length
or some value slightly larger than that.Each loop of possible length
n
(frommin_length
) does the following:creates the list of decision variables
x
of lengthn
.the minimum value of
x
is 1 and the upper value ismax_val + 1
, i.e. the domain is $\{1,\cdots,\max\_\text{val}+1\}$. The reason behind this upper value is that if the solution starts with $1$, then the largest possible difference must be the largest difference value ${}+ 1$.
The solution is thus thought of as a "normalized" version of the origin list, or rather a possible variant since there might be many different solutions where only one of then might be the same as the normalized version of the origin list.
add constraints of the list
x
as described below.if we find a solution then it is a shortest solution. Normally the model is finished after this. But there are cases where we continue to find all the solutions or perhaps all the shortest solutions. (The Picat model does quite a few experiments with this.)
The constraints in the model are:
all_different(x)
: Ensures that all the decision variables are distinct. Note that this is not really necessary since the next constraintincreasing_strict(x)
ensures this as well. For constraint programming solvers, adding this constraint seems to speed up the model.increasing_strict(x)
: Ensures that the decision variables are strictly ordered, i.e. distinct and sorted. The ordering part can be seen as a symmetry breaking to reduce a lot of symmetric solutions. The strict part is necessary for the model though.(Note: In some experiments, the strict part is skipped so we can study origin lists and difference lists that contain duplicates. This is not discussed further here.)
x[1] = 1
: the first element is $1$. This is to make the solution "normalized".x[n] = max_val
: the last element ismax_val
, i.e.1 + max(diffs)
. These two constraints make sure that the solution is "normalized".All the pair differences in the solution
x
must be in the difference listdiffs
. The pseudo code for this is:
foreach(i in 1..n, j in i+1..n)
abs(X[I]-X[J]) in diffs
end
i.e. All possible pair differences in x
must be in the difference list.
- Ensure that we cover all the differences in the difference list
diffs
. Pseudo code:
foreach(d in diffs)
% Create the indices i,j where I < J
i in 1..n,
j :: 1..n,
i < j,
d = abs(x[i]-x[j])
end
Note that i
and j
are decision variables with domain $\{1,\cdots,n\}$. For all differences d
in the difference list, we try to find some indices i
and j
(with i < j
) such that d = abs(x[i]-x[j])
.
The two constraints above ensure that the solution list x
generates all the differences in difference list diffs
as well as only those differences.
This is the end of the base model. It is - as mentioned above - implemented in Picat and it works quite well. However, it would be interesting to know alternative approaches for solving this problem.
I haven't found much about this, but perhaps the terms I searched for were not the proper ones.
One vaguely related paper is a paper by De Biasi (2014)1 about reconstruction permutations of length $N$ given a permutation of differences of length $N-1$.
However, it only handles difference lists that are permutations, but I am interested in any difference lists, not just permutations. Also, the objective of the paper is to prove that the problem is NP-complete which is not my goal here. (Here is a Picat model that solves these kind of problems.)
One other related thing is perfect rulers where the difference lists are the full list of integers $1,\cdots,N$:
Perfect rulers might be seen as a special case of what I am interested in, but the general case of difference lists is that they may be non-contiguous. And the objective is not the same: I want to recover the list that generated the differences.
Does anyone have more information about this?
Reference
[1] De Biasi, M. (2014). Permutation Reconstruction from Differences. The Electronic Journal of Combinatorics. 21(4):P4.3.
n
in the normalized list, making it prohibitively expensive to output all solutions. For instance, the number of solutions for the input[1,2,...,n]
is close to2^(n-3)
. How large, then, do you anticipaten
being? $\endgroup$