Finding permutations efficiently
Pythonic

I rewrote a few of the loops to prevent looping over the index. I also changed used_comps to a set which has O(1) containment checks. For smaller arrays this will not matter a lot, for larger ones this can make a difference.

I also moved the permutation_dict and used_comps definitions closer to the place they are used.

def find_permutation2(true, permuted):
    """
    Finds the most probable permutation of true time series in between permuted time series
    :param true: true ordered time series of shape T times X
    :param permuted: Permuted time series of shape P times T. P &gt; K
    :return: A dict containing {true idx: permuted idx}
    """

    corr_matrix = np.zeros((true.shape[1], permuted.shape[0]))

    # Find correlations
    for i, column in enumerate(true.T):
        for j, row in enumerate(permuted):
            corr_matrix[i, j] = np.corrcoef(column, row)[0, 1]

    # Find best order
    per_matrix = np.argsort(-np.abs(corr_matrix), axis=1)

    permutation_dict = {}
    used_comps = set()
    for i, row in enumerate(per_matrix):
        for j in row:
            if j in used_comps:
                continue
            permutation_dict[i] = j
            used_comps.add(j)
            break

    return permutation_dict


numba

You can use numba, which compiles the python to llvm. I'm no expert, but I got it to work with these settings.

m_jith = numba.jit(find_permutation2, looplift=False, forceobj=True)
m_jith(true, permuted)


np.setdiff1d

You can use np.setdiff1d. This will be slower for smaller arrays, but might be faster for larger arrays.

def find_permutation3(true, permuted):
    """
    Finds the most probable permutation of true time series in between permuted time series
    :param true: true ordered time series of shape T times X
    :param permuted: Permuted time series of shape P times T. P &gt; K
    :return: A dict containing {true idx: permuted idx}
    """

    corr_matrix = np.zeros((true.shape[1], permuted.shape[0]))

    # Find correlations
    for i, column in enumerate(true.T):
        for j, row in enumerate(permuted):
            corr_matrix[i, j] = np.corrcoef(column, row)[0, 1]

    # Find best order
    per_matrix = np.argsort(-np.abs(corr_matrix))

    permutation_dict = {}
    used_comps = set()
    for i, row in enumerate(per_matrix):
        j = np.setdiff1d(row, used_comps, assume_unique=True)[0]
        permutation_dict[i] = j
        used_comps.add(j)

    return permutation_dict


timings

All these things have very little effect on the speed of the algorithm

%timeit find_permutation(true, permuted)



950 µs ± 23.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



%timeit find_permutation2(true, permuted)



978 µs ± 55.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



%timeit find_permutation3(true, permuted)



1.05 ms ± 58.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



%timeit find_permutation_jit(true, permuted)



1.08 ms ± 139 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



%timeit find_permutation_cython(true, permuted)



1.06 ms ± 135 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



But this can change with a larger dataset.

This close timing is probably because the python is not the bottleneck, but the numpy operations, most likely the corrcoef, but you'll need to do some profiling to see whether this is true.