Collecting numbers in ascending order

Question

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)

Answer 1

Here are a few suggestions:

• You should get in the habit of wrapping all code that isn't contained in a function, in a main guard. This will protect the code from being run when the file is imported.
• Instead of code like, for example, s = "x" + str(i) + "x", you should use f""in front of your strings so you can directly include variable names into the strings, like so: s = f"x{i}x".
• You should include module docstrings for all your functions. This will help any documentation identify what your functions are supposed to do.
• Running your code through pylint, here are a few warnings:
  • Parameters: Having one letter parameters isn't a good practice. Your code lit up when I first pasted it into my editor. Having meaningful names for your parameters also helps remind you what your function is supposed to take in.
  • Spacing: Any spacing like s=1 or a=b+c should be spread out to s = 1 and a = b + c. This improves the readability of your code greatly.

Below is the refactored code:

def swap(array, index_one, index_two):
    """ Swaps two values in an array, then returns the new array"""
    temp = array[index_one]
    array[index_one] = array[index_two]
    array[index_two] = temp
    return array


def is_same_round(tables, element_one, element_two):
    """
    Returns True if the index of `element_one` is greater than the index
    of `element_two`
    """
    return tables.index(element_one) < tables.index(element_two)

def solve(file):
    """ Solves the 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 = f"{len(tables)} {min(roundnumbers)} {roundnumbers.count(min(roundnumbers))}"
    print(result)

if __name__ == '__main__':
    for i in range(1, 10):
        file_to_solve = f'junar{i}.in'
        solve(file_to_solve)