Python Forum
How to collect all integers with minimum number of rounds?
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?
Reply
#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.
Reply
#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.
Reply
#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.
Reply
#5
I don't understand the question. If indeed you want to think about recursion I humbly suggest another classic puzzle - Towers of Hanoi.
Reply
#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?
Reply
#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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Program that allows to accept only 10 integers but loops if an odd number was entered gachicardo 4 3,498 Feb-24-2022, 10:40 AM
Last Post: perfringo
  finding the minimum value out of a set of inputs kannan 1 5,242 Oct-30-2018, 01:52 PM
Last Post: ichabod801
  Storing Minimum List of values from a recursive function sigsegv22 1 2,481 Sep-10-2018, 01:25 PM
Last Post: ichabod801
  maximum and minimum element from the list and return output in dict MeeranRizvi 1 3,685 Jan-02-2017, 02:12 PM
Last Post: ichabod801

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020