Fast randomly-paired permutation

I need to generate a randomly-paired permutation for an ordered array of integers (indexes). For example, for N=10 the input array looks like:

[0 1 2 3 4 5 6 7 8 9]

A valid randomly-paired permutation would be:

[7 8 6 5 9 3 2 0 1 4]

Notice that the indexes are randomly-paired, i.e.: if element 0 (input array) is paired with 7 (0th position in the permuted array), then element 7 (input array) is paired with 0 (7th position in the permuted array), etc. No element in the input array can be paired with itself, i.e. this is not a valid permutation:

[7 1 6 5 9 3 2 0 8 4]

because the elements 1 and 8 are in their "index" positions. This is related to derangement permutation, a topic already covered a few times in SO:

• Generate a random derangement of a list
• Shuffle list, ensuring that no item remains in same position
• python shuffle such that position will never repeat

I'm not certain how (if) I could use any of the answers listed there to my benefit. The code below does what I need, but it becomes very slow for large N values. I need to perform this operation thousands of times for N ~ 1500, meaning this method is of no use.

I'm positive there must be a more clever way to do this.

N = 10
idxs = np.arange(N)

# Generate a shuffled array
input_idxs = idxs.copy()
np.random.shuffle(input_idxs)

# Empty array to store the final randomly paired indexes
shuffled_idxs = np.zeros(N, dtype=int)

used_idxs = []
for i in idxs:
    if i not in used_idxs:
        for j in input_idxs:
            if j not in used_idxs:
                if j != i:
                    shuffled_idxs[i] = j
                    shuffled_idxs[j] = i
                    used_idxs.append(i)
                    used_idxs.append(j)
                    break