Skip to content

Make combination space

Generates a dataset (OrderedSet) of coalitions from the permutation_space. In principle, this could be directly filled and passed to the make_shapley_values function but then the function wouldn't be pure so this will be just an empty template. Don't mix up this and the later-filled combination space. Briefly, the combination space of one permutation of (A,B,C) is something like this:

(A,B,C) (A,B) (B,C) (A,C) (C) (B) (A) ()

This will happen for every permutation of the permutation space so either there will be a large number of combinations here or if the set is small enough, it will be exhausted.

Parameters:

Name Type Description Default
permutation_space list

A list of players to be shuffled n times.

 required
pair Optional[Tuple]

pair of elements that will always be together in every combination

 None
lesioned Optional[any]

leseioned element that will not be present in any combination

 None

Returns:

Type Description
OrderedSet

Combination space as an OrderedSet of frozensets.
Source code in msapy/msa.py 
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
@typechecked
def make_combination_space(*, permutation_space: list, pair: Optional[Tuple] = None, lesioned: Optional[any] = None) -> OrderedSet:
    """
    Generates a dataset (OrderedSet) of coalitions from the permutation_space.
    In principle, this could be directly filled and passed to the make_shapley_values function
    but then the function wouldn't be pure so **this will be just an empty template**.
    Don't mix up this and the later-filled combination space.
    Briefly, the combination space of **one permutation of** (A,B,C) is something like this:

    (A,B,C)
    (A,B)
    (B,C)
    (A,C)
    (C)
    (B)
    (A)
    ()

    This will happen for every permutation of the permutation space so either there will be a large number
    of combinations here or if the set is small enough, it will be exhausted.

    Args:
        permutation_space (list):
            A list of players to be shuffled n times.

        pair (Optional[Tuple]):
            pair of elements that will always be together in every combination

        lesioned (Optional[any]):
            leseioned element that will not be present in any combination

    Returns:
        (OrderedSet): Combination space as an OrderedSet of frozensets.
    """

    _check_valid_permutation_space(permutation_space)

    # if we have an element that needs to be lesioned in every combination, then we store it in a set so that taking a difference becomes easier and efficient
    lesioned = {lesioned} if lesioned else set()

    combination_space = OrderedSet()

    # iterate over all permutations and generate including and excluding combinations
    for permutation in permutation_space:
        # we need this parameter if we have a pair so that the pair of elements are always together
        skip_next = False
        for index, element in enumerate(permutation):
            # logic to skip the next element if we encounter a pair element
            if skip_next:
                skip_next = False
                continue
            if pair and element == pair[0]:
                index += 1
                skip_next = True

            # forming the coalition with the target element
            including = frozenset(permutation[:index + 1]) - lesioned
            # forming it without the target element
            excluding = frozenset(permutation[:index]) - lesioned

            combination_space.add(including)
            combination_space.add(excluding)

    return combination_space