Has someone an idea how to solve the following problem?

Take the numbers 1,...,100000 and permute them in some way. At first you can make a swap of two numbers. Then you have to compute how many rounds it would take to collect numbers in ascending order. You have to collect numbers by every round by going left to right. How many ways there are swap two numbers at the beginning to collect numbers in ascending order with minimum number of rounds?

For example, if numbers are from one to five and those at the beginning in order 3, 1, 5, 4, 2, then you can collect them in three rounds: On first round you collect 1, 2, on the second round 3, 4 and finally 5. But you can do one swap in three different ways to collect numbers in two rounds, namely

3, 4, 5, 1, 2
3, 1, 4, 5, 2
3, 1, 2, 4, 5

Five number sequence can be solved easily by brute force and I found an algorithm to collect 1000 numbers, but 100000 numbers needs maybe some kind of trick to compute fast how a specific swap at the beginning affects how many rounds it takes to collect numbers.

My effort:

I guess the hardest part is to find a permutation that guarentee you collect the numbers with minimum number of moves. I also heard that Dilworth's theorem tells me that the minimal decomposition into ascending subsequences is equal to the size of the maximal descending subsequence. https://artofproblemsolving.com/community/c163h1906044_an_algorithm_to_collect_numbers_in_ascending_order . But i'm not sure if this is true: https://stackoverflow.com/questions/57952706/how-to-collect-numbers-in-ascending-order-with-minimal-number-of-rounds

So I have three questions:

  1. How can I compute the minimal number of rounds, as is is pretty difficult at least for me to find a swap that makes sure that collecting numbers takes the minimal number of rounds?
  2. How can I compute the number of ways I can make a swap at the beginning if I want to collect the numbers with minimal number of rounds?
  3. Does Dillworth's theorem helps to solve question 1 or 2? If it helps, how one applies it to the problem?

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.