Jun-11-2019, 03:23 PM
What kind of algorithm wold solve the following problem?
I have been given a positive integer n. Take the n first positive integers 1 to n and permute those to some order. At the beginning you can swap the position of two numbers. Each round you go through the sequence and your aim is to collect numbers from ascending order. If the original permutation is given, determine how many ways one can select two numbers from the original sequence to be swapped if one wants to collect all number with minimum number of rounds and how many rounds it would take to collect numbers in ascending order.
For example if the numbers are at the beginning 3, 1, 5, 4, 2, then you collect at the first round numbers 1 and 2, on the second round 3 and 4 and on the third round 5. So totally three rounds. But you can make a swap to make the following sequences:
3, 4, 5, 1, 2
3, 1, 4, 5, 2
3, 1, 2, 4, 5
and all of them can be collected in two rounds.
But what if n is larger than five, say about 100000?
I have been given a positive integer n. Take the n first positive integers 1 to n and permute those to some order. At the beginning you can swap the position of two numbers. Each round you go through the sequence and your aim is to collect numbers from ascending order. If the original permutation is given, determine how many ways one can select two numbers from the original sequence to be swapped if one wants to collect all number with minimum number of rounds and how many rounds it would take to collect numbers in ascending order.
For example if the numbers are at the beginning 3, 1, 5, 4, 2, then you collect at the first round numbers 1 and 2, on the second round 3 and 4 and on the third round 5. So totally three rounds. But you can make a swap to make the following sequences:
3, 4, 5, 1, 2
3, 1, 4, 5, 2
3, 1, 2, 4, 5
and all of them can be collected in two rounds.
But what if n is larger than five, say about 100000?