Combinatorics#

A collection of functions used to iterable over all possible rankings, profiles, etc…

class GSNode(cand_set)[source]#: Class used to represent nodes in a group-separable profiles.

all_anonymous_profiles(num_voters: int, num_candidates: int) → list[tuple[tuple[int]]][source]#

Returns a list of all the anonymous profiles for a given number of voters and candidates. An anonymous profile is a sorted tuple of rankings, each ranking being represented by a tuple of int. It is anonymous in the sense that the position of the voters does not matter. We implement this by sorting the rankings in the profile in lexicographic order.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)

Returns:

A list containing all the anonymous profiles

Return type:

list[tuple[tuple[int]]]

all_group_separable_profiles(num_voters: int, num_candidates: int, profiles: Iterable[Sequence[Sequence[int]]] = None) → list[tuple[tuple[int]]][source]#

Returns all profiles that are group-separable.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)
profiles (Iterable[Sequence[Sequence[int]]], defaults: None) – The collection of all profiles. If the argument is not provided, prefsampling.combinatorics.all_profiles() is used.

Returns:

A list of all the single-crossing profiles.

Return type:

list[tuple[tuple[int]]]

all_gs_structure(num_voters: int = None, num_candidates: int = None, gs_profiles: Iterable[Sequence[Sequence[int]]] = None) → list[str][source]#

Returns the group-separable structures for which at least one profile is group-separable.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)
gs_profiles (Iterable[Sequence[Sequence[int]]], defaults: None) – The collection of all group-separable profiles. If the argument is not provided, prefsampling.combinatorics.all_group_separable_profiles() is used.

Returns:

A list of all the string representations of the structure.

Return type:

list[str]

all_non_isomorphic_profiles(num_voters: int, num_candidates: int, profiles: Iterable[Sequence[Sequence[int]]] = None) → list[tuple[tuple[int]]][source]#

Returns a maximal collection of profiles that are not isomorphic. Two profiles are isomorphic if there exists a renaming of the candidates such that the two profiles are the same.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)
profiles (Sequence[Sequence[int]], defaults: None) – The collection of all profiles. If the argument is not provided, prefsampling.combinatorics.all_profiles() is used.

Returns:

A list containing all the profiles, selecting only one single profile per equivalence class.

Return type:

list[tuple[tuple[int]]]

all_profiles(num_voters: int, num_candidates: int) → list[tuple[tuple[int]]][source]#

Returns a list of all the profiles for a given number of voters and candidates. We compute this by considering all permutations of all the anonymous profiles.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)

Returns:

A list containing all the profiles

Return type:

list[tuple[tuple[int]]]

all_rankings(num_elements: int) → list[tuple[int]][source]#

Returns a list of all the rankings with num_elements.

Parameters:: num_elements (int) – The number of elements.
Returns:: The list of all the rankings with num_elements, each ranking being represented as a tuple of int.
Return type:: list[tuple[int]]

all_single_crossing_profiles(num_voters: int, num_candidates: int, profiles: Iterable[Sequence[Sequence[int]]] = None, fix_order: bool = False) → list[tuple[tuple[int]]][source]#

Returns all profiles that are single-crossing.

Parameters:

num_voters (int) – The number of voters
num_candidates (int) – The number of candidates (the length of the rankings)
profiles (Sequence[Sequence[int]], defaults: None) – The collection of all profiles. If the argument is not provided, prefsampling.combinatorics.all_profiles() is used.
fix_order (bool) – If true, only profile that are single-crossing with respect to the current ordering of the voters are considered.

Returns:

A list of all the single-crossing profiles.

Return type:

list[tuple[tuple[int]]]

all_single_peaked_circle_rankings(num_candidates: int)[source]#

Returns the list of all the single-peaked rankings with respect to the circular axis 0, 1, …, m - 1, 0.

Parameters:: num_candidates (int) – The number of candidates (the length of the rankings)
Returns:: A list containing all single-peaked on a circle rankings.
Return type:: list[tuple[int]]

all_single_peaked_rankings(num_candidates: int) → list[tuple[int]][source]#

Returns the list of all the single-peaked rankings with respect to the axis 0, 1, …, m - 1.

Parameters:: num_candidates (int) – The number of candidates (the length of the rankings)
Returns:: A list containing all single-peaked rankings.
Return type:: list[tuple[int]]

comb(n: int, k: int) → int[source]#

Function to compute the binomial coefficient. It uses math.comb if available (i.e., if Python >= 3.8), otherwise computes it by hand.

Parameters:

n (int) – n in n chooses k, i.e., the size of the whole set
k (int) – k in n chooses k, i.e.; the size of the subset

Returns:

The value of n chooses k

Return type:

int

generalised_ascending_factorial(value: int, length: int, increment: float) → float[source]#

Computes the ascending factorial. The ascending factorial is equal to: $\text{value} \times (\text{value} + \text{increment}) \times \ldots \times (\text{value} + (\text{length} - 1) \times \text{increment})$ .

Parameters:

value (int) – The value whose generalised ascending factorial we are computing.
length (int) – The number of terms in the ascending factorial to compute.
increment (float) – The increment to add to the value in each term.

Returns:

The value of the (generalised) ascending factorial.

Return type:

float

gs_structure(profile: Sequence[Sequence[int]], verbose: bool = False) → str[source]#

Computes the group-separable structure for a given profile.

Parameters:

profile (Sequence[Sequence[int]]) – The profile.
verbose (bool, defaults: None) – If True, then additional information is printed.

Returns:

A string representing the structure.

Return type:

str

is_single_crossing(profile: Sequence[Sequence[int]]) → bool[source]#

Tests whether a profile is single-crossing given the current ordering of the voters.

Parameters:: profile (Sequence[Sequence[int]]) – The profile
Returns:: True if the profile is single-crossing and false otherwise.
Return type:: bool

kendall_tau_distance(ranking_1: Iterable, ranking_2: Sequence | ndarray) → int[source]#

Computes the Kendall-Tau distance between two rankings.

Parameters:

ranking_1 (Iterable) – The first ranking
ranking_2 (Sequence | np.ndarray) – The second ranking

Returns:

The Kendall-Tau distance between the two rankings.

Return type:

int

powerset(iterable: Iterable, min_size: int = 1, max_size: int = None) → tuple[tuple][source]#

Returns the powerset of the iterable.

Parameters:

iterable (Iterable) – The iterable.
min_size (int, default: 1) – Any subset of size smaller than min_size is excluded.
max_size (int, default: len(iterable)) – Any subset of size larger than max_size is excluded.

Returns:

The powerset of the input iterable.

Return type:

tuple[tuple]

proper_powerset(iterable: Iterable, min_size: int = 1) → tuple[tuple][source]#

Returns the set of all proper subsets of the iterable.

Parameters:

iterable (Iterable) – The iterable.
min_size (int, default: 1) – Any subset of size smaller than min_size is excluded.

Returns:

The set of all subsets of the input iterable.

Return type:

tuple[tuple]

Combinatorics

Contents

Combinatorics#