Bottom Page

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
 How to collect all integers with minimum number of rounds?
#1
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?
Quote
#2
This looks like you copy-pasted your homework. What have you tried? With 7 posts I expect you to know the drill by now.
Feel like you're not getting the answers you want? Checkout the help/rules for things like what to include/not include in a post, how to use code tags, how to ask smart questions, and more.

Pro-tip - there's an inverse correlation between the number of lines of code posted and my enthusiasm for helping with a question :)
Quote
#3
(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.
Quote
#4
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.
Feel like you're not getting the answers you want? Checkout the help/rules for things like what to include/not include in a post, how to use code tags, how to ask smart questions, and more.

Pro-tip - there's an inverse correlation between the number of lines of code posted and my enthusiasm for helping with a question :)
Quote
#5
I don't understand the question. If indeed you want to think about recursion I humbly suggest another classic puzzle - Towers of Hanoi.
Quote
#6
(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?
Quote
#7
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.
Quote

Top Page

Possibly Related Threads...
Thread Author Replies Views Last Post
  finding the minimum value out of a set of inputs kannan 1 922 Oct-30-2018, 01:52 PM
Last Post: ichabod801

Forum Jump:


Users browsing this thread: 1 Guest(s)