Print the lexicographically smallest permutation that satisfies the given formation

Question

Problem Statement:

A DOTA game has N heroes, each with a distinct rank from [1..N]. In DOTA every formation is characterized as a permutation [1...N] of ranks of players. A formation is Imba when the sum of ranks of every two consecutive players is less than or equal to (N+1). Given N, you are to print the lexicographically smallest permutation of ranks [1...N] that makes the formation Imba.

Input Format

The first line will contain an integer T, i.e. the number of the test cases followed by T lines, each containing the value of N.

Constraints

• \$1 \le T \le 5\$
• \$2 \le N \le 105\$

Output Format

\$T\$ lines each containing the permutation; the numbers in each line should be seperated by a single space.

Sample Input

2
2
3

Sample Output

1 2
2 1 3

Explanation

In the first case there are two possible permutations [1,2] and [2,1]. Both of the given permutations satisfy the given constraints and [1,2] is lexicographically smaller than [2,1]. In the second case, the two possible permutations are [2,1,3] and [3,1,2], of which the former is lexicographically smaller.

Is there a more efficient way to go about doing this?

from itertools import permutations
def check_condition(perm,checksum):
    for i in range(len(perm)-1):
        if perm[i] + perm[i+1] <= checksum:
            continue
        else:
            return False
    return True
testcases = int(raw_input())
current = 1
while current <= testcases:
    max_ = int(raw_input())
    checksum = max_ + 1
    list_ = range(1,max_+1)
    for perm in permutations(list_):
        #print(perm)
        if check_condition(perm,checksum):
            print(" ".join(map(str,perm)))
            break
    current += 1

Answer 1

If you print out the solutions for the first couple of numbers, a pattern becomes obvious:

def print_first_imba(max_):
    """
    >>> print_first_imba(2)
    1 2
    >>> print_first_imba(3)
    2 1 3
    >>> print_first_imba(4)
    2 3 1 4
    >>> print_first_imba(5)
    3 2 4 1 5
    >>> print_first_imba(6)
    3 4 2 5 1 6
    >>> print_first_imba(7)
    4 3 5 2 6 1 7
    """

The pattern looks like:

• given an input sequence 1, 2, 3, ..., n, and an empty output list
• pop the last number from the sequence and prepend to the output
• pop the first number from the sequence and prepend to the output
• keep popping until there are no elements left in the sequence

That will be substantially faster than searching the permutation space.

The doc tests I wrote above should help a lot in implementing this alternative algorithm. Your current implementation passes these tests btw, if you reorganize your code to fit it into this method:

checksum = max_ + 1
list_ = range(1, max_ + 1)
for perm in permutations(list_):
    if check_condition(perm, checksum):
        print(" ".join(map(str, perm)))
        break

My alternative implementation also passes these tests:

from collections import deque

imba = deque()
highest = max_
lowest = 1
while lowest <= highest:
    imba.appendleft(highest)
    highest -= 1
    if lowest < highest:
        imba.appendleft(lowest)
        lowest += 1
print(" ".join(map(str, imba)))

In case you don't know, you can run doc tests with python -m doctest yourfile.py.

I also recommend to go a bit further and separate printing from the main logic, by renaming this method to get_first_imba and make it return perm instead of printing it.