Permutation Construct
Source: codechef
Difficulty: 1166

Permutation Construct
A permutation of length$N$is an array of length$N$that contains every integer from$1$to$N$exactly once.
Given$N$and$K$, find a permutation$P$of length$N$satisfying the following constraints:$P_i \ne i$for all$1 \le i \le N$$P_i \bmod K = i \bmod K$for all$1 \le i \le N$In case no such permutation exists, output$-1$instead.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
The first and only line of each test case contains$2$integers -$N$and$K$.
Output Format
For each test case, output the following:
If a valid permutation exists, output$N$space-separated integers -$P_1, P_2, \ldots, P_N$, representing the permutation you found.
Otherwise, output$-1$.
If there are multiple valid permutations, you may print any of them.
Constraints$1 \le T \le 100$$1 \le K \le N \le 100$Sample 1:
Explanation:
Test case$1$: All the constraints are satisfied with$P = [3, 4, 1, 2]$. For example, we can check$P_1 \ne 1$but$P_1 \bmod 2 = 1 \bmod 2 = 1$.
Test case$2$: Since$K = 1$,$P_i \bmod K = i \bmod K$holds by default. We only need$P_i \ne i$, so any permutation satisfying that works. Another possible answer is$P = [3, 1, 2]$.
Test case$3$: No valid permutation exists.

Sample Input:
4
4 2
3 1
4 3
1 1

Sample Output:
3 4 1 2
2 3 1
-1
-1

C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--> 0) {
        int n, k;
        cin >> n >> k;
        if (n<2*k) {
            cout << -1 << endl;
            continue;
        }

        bool valid = true;
        vector < int > ans;

        map < int, int> m;
        for (int i = 1; i <= k; i++) {
            int mod = i % k;
            m[mod]=(i);
        }

        int val = k+1;
        for (int i = 1; i <= n; i++) {
            if(val<=n) ans.push_back(val);
            else{
                ans.push_back(m[i%k]);
            }
            val++;
        }
        for(auto it:ans) cout<<it<<" ";
        cout<<endl;
        
    }
    return 0;

}

Go solution:
package main

import "fmt"

func solve() {
    var N, K int
    fmt.Scan(&N, &K)
    P := make([]int, N+1)
    possible := true

    for r := 0; r < K; r++ {
        var indices []int
        for i := 1; i <= N; i++ {
            if i % K == r {
                indices = append(indices, i)
            }
        }

        if len(indices) < 2 {
            possible = false
            break
        }

        for i := 0; i < len(indices)-1; i++ {
            P[indices[i]] = indices[i+1]
        }
        P[indices[len(indices)-1]] = indices[0]
    }

    if !possible {
        fmt.Println("-1")
    } else {
        for i := 1; i <= N; i++ {
            fmt.Print(P[i], " ")
        }
        fmt.Println()
    }
}

func main() {
    var T int
    fmt.Scan(&T)
    for i := 0; i < T; i++ {
        solve()
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            
            if (n == 1) {
                System.out.println("-1");
            } else if (n / k > 1) {
                StringBuilder result = new StringBuilder();
                
                for (int i = k + 1; i <= n; i++) {
                    result.append(i).append(" ");
                }
                for (int i = (n % k) + 1; i <= k; i++) {
                    result.append(i).append(" ");
                }
                for (int i = 1; i <= (n % k); i++) {
                    result.append(i).append(" ");
                }
                
                System.out.println(result.toString().trim());
            } else {
                System.out.println("-1");
            }
        }
        
        sc.close();

    }
}

JavaScript solution:
const readline = require("readline");

const inputOutputInterface = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
let currentIndex = 0;

inputOutputInterface.on("line", (line) => {
    inputLines.push(line);
}).on("close", () => {
    executeTestCases();
});

function readNextInteger() {
    return parseInt(inputLines[currentIndex++]);
}

function readNextIntegerArray() {
    return inputLines[currentIndex++].split(" ").map(Number);
}

function executeTestCases() {
    let numberOfTests = readNextInteger();

    while (numberOfTests--) {
        let [arrayLength, modulusValue] = readNextIntegerArray();
        let permutationArray = new Array(arrayLength + 1).fill(0);
        let isPossible = true;

        for (let remainder = 0; remainder < modulusValue; remainder++) {
            let indices = [];

            for (let num = 1; num <= arrayLength; num++) {
                if (num % modulusValue === remainder) {
                    indices.push(num);
                }
            }

            if (indices.length === 1) {
                isPossible = false;
                break;
            }

            for (let j = 0; j < indices.length; j++) {
                let currentIndexPos = indices[j];
                let nextIndexPos = indices[(j + 1) % indices.length];
                permutationArray[currentIndexPos] = nextIndexPos;
            }
        }

        console.log(isPossible ? permutationArray.slice(1).join(" ") : "-1");
    }
}

Python solution:
def solve():
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        mod_groups = [[] for _ in range(K)]
        for i in range(1, N + 1):
            mod_groups[i % K].append(i)
        
        possible = all(len(group) > 1 for group in mod_groups)
        if not possible:
            print(-1)
            continue
        
        # Shift each group to avoid fixed points
        P = [0] * (N + 1)
        for group in mod_groups:
            sz = len(group)
            for i in range(sz):
                P[group[i]] = group[(i + 1) % sz]
        
        print(' '.join(str(P[i]) for i in range(1, N + 1)))


solve()

Ruby solution:
def solve_permutation
  # Read number of test cases
  test_count = gets.to_i
  
  test_count.times do
    # Read n and k values
    n, k = gets.split.map(&:to_i)
    
    # Initialize groups for modulo k values
    groups = Array.new(k) { [] }
    
    # Populate groups with numbers 1..n based on their modulo k
    (1..n).each do |num|
      groups[num % k] << num
    end
    
    # Check if permutation is possible (each group needs at least 2 elements)
    valid = groups.all? { |group| group.size >= 2 }
    
    unless valid
      puts -1
      next
    end
    
    # Initialize permutation array
    permutation = Array.new(n + 1, 0)
    
    # Construct permutation by shifting elements within each group
    groups.each do |group|
      group.each_with_index do |num, index|
        permutation[num] = group[(index + 1) % group.size]
      end
    end
    
    # Output the permutation (elements 1 through n)
    puts permutation[1..n].join(' ')
  end
end

solve_permutation