Perfect Permutation (Codeforces 1711A)
Tags: Others, constructive algorithms

You are given a positive integer $$$n$$$.The weight of a permutation $$$p_1, p_2, \ldots, p_n$$$ is the number of indices $$$1\le i\le n$$$ such that $$$i$$$ divides $$$p_i$$$. Find a permutation $$$p_1,p_2,\dots, p_n$$$ with the minimum possible weight (among all permutations of length $$$n$$$).A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follows.The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a line containing $$$n$$$ integers $$$p_1, p_2,\dots, p_n$$$ so that the permutation $$$p$$$ has the minimum possible weight.If there are several possible answers, you can print any of them.

Note: In the first test case, the only valid permutation is $$$p=[1]$$$. Its weight is $$$1$$$.In the second test case, one possible answer is the permutation $$$p=[2,1,4,3]$$$. One can check that $$$1$$$ divides $$$p_1$$$ and $$$i$$$ does not divide $$$p_i$$$ for $$$i=2,3,4$$$, so the weight of this permutation is $$$1$$$. It is impossible to find a permutation of length $$$4$$$ with a strictly smaller weight.

Sample Inputs:
2
1
4

Sample Outputs:
1
2 1 4 3

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            perm = ''
            if n % 2 == 0:
                for j in range(1, n // 2 + 1):
                    perm += '{} {} '.format(2 * j, 2 * j - 1)
            else:
                perm = '{} '.format(n)
                for j in range(1, (n + 1) // 2):
                    perm += '{} {} '.format(2 * j - 1, 2 * j)
            result.append(perm)
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
test_case = int(input())
nums = []
for k in range(test_case):
    num = int(input())
    nums.append(num)
for k in range(test_case):
    ans = []
    if nums[k] == 1:
        print(1)
    else:
        for i in range(1, nums[k]):
            ans.append(i + 1)
        ans.append(1)
        print(' '.join(map(str, ans)))

Solution (Python):
import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
    n = int(inp())
    print(' '.join([str(i + 1) if i < n else '1' for i in range(1, n + 1)]))