Abbinamento bipartito massimo
Trova un abbinamento di cardinalità massima tra due gruppi di al massimo 32 vertici tramite insiemi di archi consentiti.
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)Modelli
Configura un endpoint compatibile con OpenAI o Anthropic usando URL di base e chiave API, se necessaria. Prova la connessione. Il server locale deve essere in esecuzione; gli strumenti remoti possono trasmettere dati separatamente.
Progetto
Prova vertici isolati e riassegnazione lungo un cammino aumentante, rifiutando indici non validi senza alterare gli insiemi.
Controlla prima di applicare
Confronta il comportamento effettivo con il risultato atteso. Se una verifica fallisce, indaga la causa prima di altre modifiche.
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)Chiarisci l'obiettivo dell'assegnazione prima di modificare il codice
MatchOriel è un ambiente di programmazione con IA per Windows per discutere la logica di assegnazione nel contesto dell'applicazione che la usa. Apri il progetto sorgente e spiega cosa rende ammesso un abbinamento e cosa deve ottimizzare il risultato. Chiedi all'assistente collegato di esaminare come questi requisiti compaiono nella struttura di input e nel codice prima di proporre modifiche.
Un problema di abbinamento di cardinalità massima offre un esempio. Fornisci le coppie ammesse e descrivi se l'obiettivo è semplicemente assegnare il maggior numero possibile di elementi. Chiedi al modello di esaminare un caso in cui una scelta precedente deve essere riassegnata per raggiungere quell'obiettivo. Esplicita le graduatorie di preferenza o altre regole aziendali se servono all'applicazione, perché non sono garantite dalla dimensione di un abbinamento.
Esamina la proposta e verifica che le coppie restituite corrispondano ad archi validi e che ogni elemento compaia una sola volta. Includi elementi scollegati e indici rifiutati nei controlli del tuo progetto, quindi esamina come i chiamanti gestiscono le voci non assegnate. MatchOriel supporta connessioni a endpoint compatibili con OpenAI o Anthropic, con credenziali dove richieste. I modelli senza restrizioni sono selezionabili dove il tuo servizio li offre; continuano ad applicarsi le regole del fornitore e le capacità di contesto e strumenti del server. Usa l'obiettivo dichiarato, anziché la sicurezza dell'assistente, per valutare se la modifica è appropriata.
Revisione delle assegnazioni tra coppie ammesse
L'abbinamento più grande rispetta anche le preferenze?
Non automaticamente. Il compito illustrato massimizza il numero di assegnazioni fra le coppie ammesse. Se contano la stabilità delle preferenze o la qualità ponderata, specificalo separatamente e verifica se l'algoritmo proposto affronta quell'obiettivo anziché solo il conteggio.
Perché includere un caso che richiede una riassegnazione?
Distingue una soluzione capace di rivedere le scelte precedenti da una passata greedy che potrebbe fermarsi troppo presto. Fornisci il numero atteso di coppie e alternative valide, poi esamina il codice proposto e il suo output rispetto a quegli esempi.
I test devono richiedere un insieme esatto di coppie?
Solo quando il contratto richiede quel risultato specifico. Più assegnazioni possono soddisfare lo stesso obiettivo di cardinalità massima. Verifica validità, unicità degli elementi e dimensione, e documenta gli eventuali requisiti di ordinamento o risoluzione dei pareggi prima di rendere più rigidi i casi di prova.
Come devono arrivare al chiamante gli elementi non assegnati?
Definisci se il chiamante li ricava dalle coppie mancanti o si aspetta una rappresentazione esplicita. Esamina quel confine insieme alla struttura restituita, poi verifica input scollegati affinché l'applicazione non tratti un elemento legittimamente non assegnato come un errore di analisi.
MatchOriel · Aggiornato 2026-10-25