Couplage biparti maximum
Trouvez un couplage de cardinalité maximale entre deux groupes de 32 sommets au plus à partir des arêtes autorisées.
def maximum_matching(edges, right_count):
if type(right_count) is not int or not 0 <= right_count <= 32 or type(edges) not in (list, tuple) or len(edges) > 32:
raise ValueError("matching.size")
if any(type(row) not in (set, frozenset) or any(type(v) is not int or not 0 <= v < right_count for v in row) for row in edges):
raise ValueError("matching.edge")
owners = [-1] * right_count
def augment(left, seen):
for right in sorted(edges[left]):
if right in seen:
continue
seen.add(right)
if owners[right] == -1 or augment(owners[right], seen):
owners[right] = left
return True
return False
for left in range(len(edges)):
augment(left, set())
return sorted((left, right) for right, left in enumerate(owners) if left != -1)Modèles
Configurez un endpoint compatible OpenAI ou Anthropic avec son URL de base et une clé API si nécessaire. Testez la connexion. Un serveur local doit fonctionner ; les outils distants peuvent transmettre des données séparément.
Projet
Testez les sommets isolés et la réaffectation par chemin augmentant, en refusant les indices invalides sans modifier les ensembles.
Vérifiez avant d’appliquer
Comparez le comportement observé au résultat attendu. Si une vérification échoue, cherchez la cause avant de poursuivre les modifications.
def maximum_matching(edges, right_count):
if type(right_count) is not int or not 0 <= right_count <= 32 or type(edges) not in (list, tuple) or len(edges) > 32:
raise ValueError("matching.size")
if any(type(row) not in (set, frozenset) or any(type(v) is not int or not 0 <= v < right_count for v in row) for row in edges):
raise ValueError("matching.edge")
owners = [-1] * right_count
def augment(left, seen):
for right in sorted(edges[left]):
if right in seen:
continue
seen.add(right)
if owners[right] == -1 or augment(owners[right], seen):
owners[right] = left
return True
return False
for left in range(len(edges)):
augment(left, set())
return sorted((left, right) for right, left in enumerate(owners) if left != -1)Précisez l’objectif d’affectation avant de modifier le code
MatchOriel est un espace de programmation assistée par IA sous Windows pour discuter de la logique d’affectation dans le contexte de l’application qui l’utilise. Ouvrez le projet source et expliquez ce qui autorise une paire et ce que le résultat doit optimiser. Demandez à l’assistant connecté d’examiner comment ces exigences figurent dans la structure d’entrée et dans le code avant de proposer des modifications.
Une tâche de couplage de cardinalité maximale fournit un exemple. Présentez les paires autorisées et précisez si le but consiste simplement à affecter le plus grand nombre possible de membres. Demandez au modèle d’examiner un cas où il faut revenir sur un choix antérieur pour atteindre ce but. Explicitez le classement des préférences ou les autres règles métier si votre application en a besoin : la taille d’un couplage ne les établit pas.
Examinez la proposition et vérifiez que les paires renvoyées correspondent à des arêtes valides et à des appartenances uniques. Incluez les membres isolés et les indices rejetés dans les vérifications de votre projet, puis examinez comment le code appelant traite les entrées non affectées. MatchOriel prend en charge les connexions aux points de terminaison compatibles OpenAI ou Anthropic, avec les identifiants nécessaires. Des modèles sans restrictions sont sélectionnables si votre service les propose ; les règles du fournisseur et les capacités de contexte et d’outils du serveur restent applicables. Évaluez la pertinence de la modification selon l’objectif énoncé plutôt que selon l’assurance de l’assistant.
Examiner les affectations par paires autorisées
Le couplage le plus grand respecte-t-il aussi les préférences ?
Pas automatiquement. La tâche illustrée maximise le nombre d’affectations parmi les paires autorisées. Si la stabilité des préférences ou une qualité pondérée compte, précisez-le séparément et vérifiez si l’algorithme proposé répond à cet objectif plutôt qu’au seul nombre.
Pourquoi inclure un cas nécessitant une réaffectation ?
Il distingue une solution capable de réviser des choix antérieurs d’un passage glouton qui peut s’arrêter trop tôt. Fournissez les nombres de paires attendus et des alternatives valides, puis examinez le code proposé et sa sortie à l’aide de ces exemples.
Les tests doivent-ils imposer un ensemble exact de paires ?
Uniquement si le contrat exige ce résultat précis. Plusieurs affectations peuvent satisfaire le même objectif de cardinalité maximale. Vérifiez la validité, l’unicité des appartenances et la taille, puis documentez toute exigence d’ordre ou de départage avant de rendre les jeux de test plus stricts.
Comment présenter les membres non affectés au code appelant ?
Définissez si le code appelant les déduit des paires absentes ou attend une représentation explicite. Examinez cette interface avec la structure renvoyée, puis testez des entrées déconnectées afin que l’application ne traite pas un membre légitimement non affecté comme un échec d’analyse.
MatchOriel · Mis à jour 2026-10-25