Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p\_i-p\_j\mod N,\quad i\ne j$$
Now let $a\_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N −
1$), then we have a set $$A=\{a\_1,a\_2,...,a\_{N-1} \}$$
As you know given $P$ and $N$, it is easy to build $A$. Although given $A$ and $K$ there could be many $P$'s leading to $A$ or even no possible $P$ leading to $A$.


I want to know, given $A$ and $K$, is there any algorithm returning $P$ ?



Difference Sets
A keyword in this area is *[homometric](http://en.wikipedia.org/wiki/Homometric_structures)*, and a key paper this one:



> 
> Joseph Rosenblatt and Paul D. Seymour.
>  "The Structure of Homometric Sets."
>  *SIAM. J. on Algebraic and Discrete Methods*, **3**, 343-350, 1982.
>  ([PDF download](http://epubs.siam.org/doi/pdf/10.1137/0603035))
> 
> 
> 


The precise question you pose---an algorithm---is called the *beltway reconstruction
problem* in this paper:



> 
> Skiena, Steven S., Warren D. Smith, and Paul Lemke. "Reconstructing sets from interpoint distances." *Proceedings 6th Symposium on Computational Geometry*. ACM, 1990. ([ACM link](http://dl.acm.org/citation.cfm?id=98598)). Later (much later!) published in *Discrete and Computational Geometry*. Springer. Berlin, Heidelberg, 2003. 597-631.
> 
> 
> 


They provide a worst-case exponential algorithm which nevertheless runs fast under probabilistic assumptions,
and proved many variants NP-hard, but not your particular variant. 
Another, later paper on this topic is below, but I don't think it settled the
1-dimensional reconstruction problem:



> 
> R.J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays. *Discrete Math.* 202 (1999), no. 1-3, 45-71; [DOI: 10.1016/S0012-365X(98)00347-1](http://dx.doi.org/10.1016/S0012-365X(98)00347-1).
> 
> 
> 


It may be that the computational complexity of the beltway reconstruction problem remains open...?


See also the earlier MO question, "[Largest pair of homometric Golomb rulers](https://mathoverflow.net/q/31741/6094)?" 


