# Print the lexicographically smallest permutation that satisfies the given formation

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


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.