2
$\begingroup$

Giving a list with $n$ elements, in how many ways can this list be unsorted (Where an unsorted list is defined as a list in which no two adjacent elements are sorted. I.e any two adjacent elements will not be adjacent in the sorted list. As opposed to non-sorted list in which the list is merely non sorted).

Not all lists can be unsorted. In particular if the number of elements in the list $n$ minus the number of repetitions $r$ in the list is less than or equal to 3, the list can't be unsorted. I.e if

$$n - r \le 3$$

Giving the above, I'm interested only in the maximum number of unsorted lists that can be generated from a list of length $n$

Take the list:

$$\{1,2,3,4,5\}$$

Two possible unsorted variants are:

$$\{1,3,5,2,4\}$$

$$\{1,4,2,5,3\}$$

Or even better, the list:

$$\{1,2,3,4\}$$

Can be unsorted into two possible permutations: $$\{3,1,4,2\}$$

$$\{2,4,1,3\}$$

$\endgroup$
2
  • $\begingroup$ Can you place an example of what unsorted means, is not very clear what do you mean by "adjacent elements are sorted". $\endgroup$ – Phicar Dec 4 '16 at 22:38
  • $\begingroup$ Question has been edited for clarity. Why is it downvoted? $\endgroup$ – Tobi Alafin Dec 4 '16 at 22:52
1
$\begingroup$

This sounds like a question that is very hard to get right, though I would love to be proven wrong. Here is an extremely handwavy approach to the asymptotic value for large $n$. We want to figure the probability that a random permutation will be acceptable. Imagine placing numbers in the odd positions first, then filling the even ones. Nothing can go wrong during the odd position fill. If you fill an even position randomly, you have about $\frac 4n$ chance that it will be next to one of the neighboring numbers and $\frac {n-4}n$ that it will not be. We have $\frac n2$ even slots to fill, so the chance a random permutation is acceptable is about $\left( 1-\frac 4n\right)^{n/2}=\left( 1-\frac 2{n/2}\right)^{n/2}$. The limit of this as $n$ gets large is $e^{-2}$. We have ignored end effects, the chance that two neighboring odd slots share a neighbor, the chance that two neighboring odd slots are neighbors, and correlations between the chance that one placement fails and another fails.

$\endgroup$
2
  • $\begingroup$ Hello Ross Milikan, have you discovered an exact way to solve this problem? $\endgroup$ – Tobi Alafin Dec 10 '16 at 21:55
  • $\begingroup$ @TobiAlafin: no, no further inspiration, but I did write a simulation program. For $n=100$ and $1000$ it does come out close to $e^{-2}$ in runs of $10,000$ and $100,000$ $\endgroup$ – Ross Millikan Dec 11 '16 at 1:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.