random_test_dim_curse.py

import numpy as np
from scipy.optimize import linprog


RETRIES = 1000
DIM = 100
SAMPLES = 42

results = []

for _ in range(RETRIES):
	# sample items
	X = np.random.rand(SAMPLES, DIM)

	# build inequalities
	A = []
	for p1 in range(len(X)):
		for p2 in range(len(X)):
			if p1>=p2: continue
			A.append( X[p1]-X[p2] )
	A = np.array(A)
	b = np.zeros(A.shape[0]) 
	c = np.zeros(DIM)

	# solve inequalities
	res = linprog(c, A_ub=A, b_ub=b)
	axis = res.x

	# check the solution:
	# - project items
	vals = []
	for idx,t in enumerate(X):
		vals.append( np.dot(axis,t) )
	# - count inversions
	inversions = 0
	for c1 in range(len(vals)):
		for c2 in range(len(vals)):
			if c1<c2 and vals[c1]>=vals[c2]:
				inversions += 1

	results.append( inversions )

print(f"""SAMPLES {SAMPLES}\tDIM {DIM}\tRETRIES {RETRIES}
mean inversions {np.mean(results)}\t number of tries with inversions {sum([1 for c in results if c>0])/RETRIES}""")