1
$\begingroup$

Consider all the permutations of the first $n$ natural numbers. From each permutation we can form a multiset of integers (which I call a gap multiset) consisting of all the absolute differences of each adjacent pair in the permutation.

For example if $n=6$ we have $n!=120$ such permutations. The permutation (1,2,3,4,5,6) produces the gap multiset {1,1,1,1,1} and (1,6,2,5,3,4) produces the gap mutliset {1,2,3,4,5}.

There are three obvious conditions for a gap multiset of a permutation of the first $n$ natural numbers:

  1. The multiset must have a cardinality of $n-1$.
  2. The elements must be integers between $1$ and $n-1$ inclusive.
  3. Each of the integers $m$, where $0<m<n$, have a maximum multiplicity of $n-m$.

So for example if n=6 then due to condition 3 you can only have one 5, since it can only be formed from 6-1=5.

These conditions are necessary but not sufficient for a multiset to be a gap multiset. For example if $n=6$ the following multisets fulfill all the conditions above but are not gap multisets:

  • {3,3,4,4,5}
  • {3,3,3,4,5}
  • {2,3,4,4,5}
  • {2,2,3,4,5}
  • {2,2,2,4,4}
  • {2,2,2,2,4}
  • {1,3,4,4,5}

In another example, if n=10 then:

  • {1,1,1,1,1,7,8,8,9} is NOT a gap multiset
  • {1,1,1,1,1,7,7,8,9} is a gap multiset, corresponding to 4 permutations

Can you give succinct conditions which are sufficient for a multiset to be a gap multiset? I.e. given a multiset, can you give an algorithm that decides whether or not it is a gap multiset, which does not involve a search?

$\endgroup$
  • $\begingroup$ It is very simple to make an algorithm to check for the gap condition without exhaustive search over permutations. After all, there is a small set of candidate numbers consistent with the first gap, and so on for subsequent gaps, each search pruned by the candidates for earlier gaps. The algorithm can be represented as a tree search. $\endgroup$ – David G. Stork Mar 30 '18 at 20:23
  • $\begingroup$ @DavidG.Stork I meant without using such a search, I should have made myself clearer $\endgroup$ – user2882061 Mar 30 '18 at 20:32
  • $\begingroup$ Without any search?? I can't prove it (easily), but I'm willing to bet a lot of money that it is impossible... or that any "best" algorithm (e.g., linear programming) is equivalent in all relevant ways to a search, for instance of the form I outlined. $\endgroup$ – David G. Stork Mar 30 '18 at 20:44
  • $\begingroup$ I have noticed for n<=10 that multisets with n-4 or more 1s are always a gap multiset, provided the 3 stated conditions are true $\endgroup$ – user2882061 Mar 30 '18 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.