Python Forum

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?

This looks like you copy-pasted your homework. What have you tried? With 7 posts I expect you to know the drill by now.

(Jun-11-2019, 06:08 PM)micseydel Wrote: [ -> ]This looks like you copy-pasted your homework. What have you tried? With 7 posts I expect you to know the drill by now.

How do you prove that this is a homework rather than for example a puzzle that everybody can solve other places than home? I tried to think about recursion.

It doesn't matter if it's homework, you need to put in effort. Trying to avoid doing work doesn't look good for your credibility.

I don't understand the question. If indeed you want to think about recursion I humbly suggest another classic puzzle - Towers of Hanoi.

(Jun-11-2019, 07:48 PM)jefsummers Wrote: [ -> ]I don't understand the question.

What part of the question needs to be written more clearly?

From description, you would simply collect the two lowest numbers (the minimums in the range). Why swap? What are the restrictions on collecting numbers (if you are to "collect numbers from ascending order" why not just remove the two lowest numbers from the list)? From what was described, I don't see a reason for recursion.