2つの不等なリストをペアでペアリングするアルゴリズム

Question

学生と教師という2つの不等なサイズのリストを持つアルゴリズムを作成する必要があります。教師よりも多くの生徒がいます。私は各生徒のペアリングを作成する必要があります。各生徒はほぼ同じ生徒数に対応しています。

合併症は、私が受け入れられないペアリングのコレクションを持っているということです。具体的には、各生徒は、ペアにできない1人以上の教師を持つことができます。

私は、各教師が割り当てられている生徒の数が正確である必要はないので、無作為にマッチングを開始し、一致しないマッチングをスキップする非常に効率的な貪欲アルゴリズムを実行できることはわかっています。それにかかわらず、私はこれを行うための効率的かつ完全な方法が大好きです。あなたが提供できるアドバイスありがとう！

Answer 1

私は最も限定的なマッチングから始まり、制限が少ないものから最後までマッチングを無制限にして、バランスを取るために使うことができます。