random_test_dim_curse.py

%%time
from itertools import combinations as _combu

import numpy as np
from scipy.optimize import linprog

def inversions(X):
    # build inequalities
    A = [v2 - v1 for v2, v1 in _combu(X, 2)]

    A = np.asarray(A)
    b, c = np.zeros(A.shape[0]), np.zeros(A.shape[1])

    # solve inequalities
    axis = linprog(c, A_ub=A, b_ub=b).x
    
    # check the solution:
    # - project items
    vals = np.dot(X, axis)
    # - count inversions
    return sum(1 for v2, v1 in _combu(vals, 2) if v2 >= v1)

RETRIES = 16
DIM, SAMPLES = 50, 32
S = np.random.rand(RETRIES, SAMPLES, DIM)
results = list(map(inversions, S))
mean_res = sum(results) / RETRIES
ntries = sum(c > 0 for c in results) / RETRIES

print(f"""SAMPLES {SAMPLES}\tDIM {DIM}\tRETRIES {RETRIES}""")
print(f"""mean inversions {mean_res}\t number of tries with inversions {ntries}""")