What kind of algorithm wold solve the following problem from https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=junar ?
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 the original sequence 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? The cases are listed in https://www.ohjelmointiputka.net/tiedostot/junar.zip . Each file contains first the number of numbers and the next lines gives the numbers in some order.
Express the solution of each file as form
a b c
where a is the number of numbers to be collected, b is the smallest number of rounds that takes to collect all numbers if you swap at the beginning one pair of numbers, and c denotes how many ways you can swap at the beginning two numbers so that you can collect numbers in ascending order with minimum number of rounds. So the answer to the example 3, 1, 5, 4, 2
should be 5 2 3
.
My brute force solution is as follows. First download the file in the link above to your computer and unzip it.
def swap(A,i,j):
temp = A[i]
A[i] = A[j]
A[j] = temp
return A
def is_same_round(tables,i,j):
return tables.index(i) < tables.index(j)
def solve(file):
tables = [line.strip('\n') for line in open(file)]
for i in range(len(tables)):
tables[i]=int(tables[i][0:len(tables[i])-1])
tables = tables[1:len(tables)]
roundnumbers = []
for i in range(len(tables)):
for j in range(i+1,len(tables)):
rounds = 1
tables = swap(tables,i,j)
for luku in range(1,len(tables)):
if not is_same_round(tables,luku,luku+1):
rounds += 1
roundnumbers.append(rounds)
tables = swap(tables,i,j)
result = ""
result += str(len(tables))
result += " "
result += str(min(roundnumbers))
result += " "
result += str(roundnumbers.count(min(roundnumbers)))
print(result)
for i in range(1,10):
file = 'junar'+str(i)+'.in'
solve(file)