CorsortBorda

class corsort.CorsortBorda(compute_history=False, record_leq=False, final_scorer=<function scorer_rho>)[source]

Corsort based on the Borda score.

Examples

>>> np.random.seed(22)
>>> n = 15
>>> perm = np.random.permutation(n)
>>> corsort = CorsortBorda(compute_history=True)
>>> corsort(perm).n_comparisons_
38
>>> entropy_bound(n)  
40.24212...
>>> corsort.history_distances_ 
[76, 64, 76, 74, 74, 72, 64, 58, 56, 54, 56, 52, 58, 56, 44, 36, 28, 30, 30, 28, 22, 20, 20, 20, 18, 10,
 12, 12, 16, 12, 10, 10, 8, 4, 4, 4, 2, 4, 2]
>>> corsort.__name__
'corsort_borda'

apply_i_lt_j(i, j)

Assuming perm[i] < perm[j], update the poset accordingly.

Parameters:

i (int) – Index of the small item.
j (int) – Index of the big item.

Examples

>>> corsort = Corsort()
>>> corsort.n_ = 4

Assume that we know perm[0] < perm[1], and perm[2] < perm[3]:

>>> corsort.leq_ = np.array([
...     [ 1,  1,  0,  0],
...     [-1,  1,  0,  0],
...     [ 0,  0,  1,  1],
...     [ 0,  0, -1,  1],
... ])

Assume we learn that perm[1] < perm[2]:

>>> corsort.apply_i_lt_j(1, 2)
>>> corsort.leq_
array([[ 1,  1,  1,  1],
       [-1,  1,  1,  1],
       [-1, -1,  1,  1],
       [-1, -1, -1,  1]])

Now we know the full order by transitivity.

compare_and_update_poset(i, j)

Perform a comparison between perm[i] and perm[j], and update the poset accordingly.

Parameters:

i (int) – First index.
j (int) – Second index.

distance_to_sorted_array()

Distance to sorted array.

Returns:: Distance between the current estimation and the sorted array.
Return type:: int

property history_comparisons_values_

History of the pairwise comparisons, in terms of compared values. Tuple (x, y) means that items of values x and y were compared, and that x < y.

Type:: list of tuple

next_compare()[source]

Iterator of pairwise comparisons to make.

Returns:: An iterator of pairwise comparisons to make.
Return type:: iterable

test_i_lt_j(i, j)

Test whether perm[i] < perm[j].

Parameters:

i (int) – First index.
j (int) – Second index.

Returns:

True if item of index i is lower than item of index j.

Return type:

bool

Notes

The history of distance is computed just before the comparison. Hence it should be computed a last time at the end of the algorithm.

update_position_estimates()

Update position estimate of each item.

Examples

>>> corsort = Corsort(final_scorer=scorer_delta)
>>> corsort.n_ = 4
>>> corsort.leq_ = np.array([
...     [ 1,  1,  1,  1],
...     [-1,  1, -1, -1],
...     [-1,  1,  1,  0],
...     [-1,  1,  0,  1],
... ])
>>> corsort.update_position_estimates()
>>> corsort.position_estimates_
array([-3,  3,  0,  0])