from hypothesis import given, assume
from hypothesis.strategies import lists, permutations
from collections import Counter, defaultdict

# Wikipedia: Paradoxe de Condorcet / Scrutin de Condorcet.
# Ici, on va observer un paradoxe classique en théorie des votes juste en utilisant Hypothesis.
# Imaginez, ici que vous fabriquez un algorithme de couplage, type APB/Admissions Parallèles/Parcoursup.

# On se donne par Hypothesis au moins trois candidats et trois voteurs.
@given(lists(permutations(["A", "B", "C"]), min_size=3))
def test_condorcet_paradox(election):
    all_candidates = {"A", "B", "C"}

    # On calcule les préférences paires à paires (u, v) de chaque candidat.
    counts = Counter()
    for vote in election:
        for i, vi in enumerate(vote):
            for j in range(i + 1, len(vote)):
                counts[(vi, vote[j])] += 1

    # On regarde quelle paires de candidats a la majorité.
    graph = defaultdict(set)
    for i in all_candidates:
        for j in all_candidates:
            if counts[(i, j)] > counts[(j, i)]:
                graph[i].add(j)

    # Maintenant, on vérifie que les préférences sont transitives, i.e. si A préfère B, B préfère C, alors A préfère C non?
    for x in all_candidates:
        for y in graph[x]:
            for z in graph[y]:
                # vérifions que x n'est pas dans graph[z]
                assert x not in graph[z]
