+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: How to collect all integers with minimum number of rounds? (/thread-19044.html)
How to collect all integers with minimum number of rounds? - meknowsnothing - Jun-11-2019
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?
RE: How to collect all integers with minimum number of rounds? - micseydel - Jun-11-2019
This looks like you copy-pasted your homework. What have you tried? With 7 posts I expect you to know the drill by now.
RE: How to collect all integers with minimum number of rounds? - meknowsnothing - Jun-11-2019
(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.
RE: How to collect all integers with minimum number of rounds? - micseydel - Jun-11-2019
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.
RE: How to collect all integers with minimum number of rounds? - jefsummers - Jun-11-2019
I don't understand the question. If indeed you want to think about recursion I humbly suggest another classic puzzle - Towers of Hanoi.
RE: How to collect all integers with minimum number of rounds? - meknowsnothing - Jun-11-2019
(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?
RE: How to collect all integers with minimum number of rounds? - jefsummers - Jun-11-2019
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.