# Permutation Array

Hello I have a problem and would like a help to prove if it is P or not.

Given an array $$\mathcal{A}$$ of integers. Is there a permutation of the elements of $$\mathcal{A}$$ such that, $$\forall i \in \{1, ..., |\mathcal{A}|-1\} : \mathcal{A}[i] \neq \mathcal{A}[i + 1]$$?

Could anyone give me some direction on how to show if it's Polynomial or not?

• Please do not delete your question after you have received a useful reply. We want questions and answers available in order to not only help you, but also others who have similar questions. Dec 11 '20 at 11:25

Suppose for simplicity that the number $$n=2k$$ of elements in the array is even. Let $$a$$ be the (one of the) most frequent element(s) and let $$m$$ the number of occurrences of $$a$$ in $$\mathcal{A}$$.
A polynomial time algorithm that solves your problem is the following: return "yes" if $$m \le k$$, otherwise return "no".
To see this notice that if $$m>k$$ the answer is trivially now, since two occurrences $$a$$ must necessarily be adjacent in any permutation of $$\mathcal{A}$$.
If $$m=k$$ then the answer is trivially yes: just interleave the copies of $$a$$ with the other elements in $$\mathcal{A}$$.
If $$m < k$$, then consider the elements of $$\mathcal{A}$$ in nonincreasing order of their number of occurrences. Create the permutation $$B$$ of $$\mathcal{A}$$ by first filling in all odd indices and then all even indices (indices start from $$1$$). For each distinct element $$x \in \mathcal{A}$$, let $$i$$ be the index of the first occurrence of $$x$$ in $$B$$. If $$i=1$$ or $$i$$ is even, then no pair of elements equal to $$x$$ can possibly be adjacent in $$B$$. Suppose then that $$i$$ is odd and that $$i>1$$. In order for $$B[i-1]$$ to be equal to $$x$$, at least $$k$$ copies of $$x$$ would be needed, but at most $$m \le k-1$$ copies are available.