Corsort

class corsort.Corsort(compute_history=False, record_leq=False, final_scorer=<function scorer_rho>)

Corsort.

Parameters:

• compute_history (bool) – If True, then compute the history of the distance to the sorted array.

• record_leq (bool) – If True, then record all the states of the leq_ matrix.

• final_scorer (callable) – Scorer used to compute the tentative estimate of the sorted list.

leq_

Matrix of size (n_, n_). Coefficient (i, j) is +1 if we know perm_[i] <= perm_[j], -1 if we know perm_[i] > perm_[j], 0 if we do not know the comparison between them.

Type:

ndarray.

position_estimates_

For each index (in the original list), its position estimate in the sorted list. Note that a position of 0 means the start of the sorted list, i.e. smallest element, whereas a position of n - 1 means the end of the sorted list, i.e. the greatest element. In other words, the position estimates are the Borda scores.

Type:

list of float

Notes

Cf. also the attributes defined in the parent class Sort.

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()

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])