从预先存在的 n-n 关系（如果存在）中找到随机 [0,1]-1 配对的算法

Question

我在Google上只能找到“稳定的婚姻”等等，但这些都不能描述我想要的。

我有这个作为输入:

A - 2, 3, 5
B - 1, 4, 2
C - 2
D - 1, 5, 4, 3

我想随机（这对我的情况非常重要） select 右侧的一个元素对应左侧的每个元素。但是：可以没有重复，但是，第 2 组（右侧）的元素可以没有伙伴。

有效示例输出：

A -> 3
B -> 1
C -> 2
D -> 4

The fact 5 is not represented anywhere is okay.

无效输出：

A -> 2
B -> 1
C -> 2
D -> 4

Because A and C both go to 2
___

A -> None
B -> 1
C -> 2
D -> 4

Because A has no partner
__

A -> 4
B -> 1
C -> 2
D -> 5

Because A doesn't "like" 4.

我知道这不会对每个初始状态都有答案。这是已知解决方案的已知问题/已证明无法解决？

编辑：随机化本身不一定是“好”的。只要它“合理地”不会每次都产生类似的结果（至少在可以帮助的时候），这对我来说就足够了。

Answer 1

经过又一个小时的谷歌搜索和掉进图论的兔子洞后，我找到了一个 github 存储库，其中包含 Hopcroft-Karp 算法的修改版本：

https://github.com/slaypni/randomized-hopcroft-karp

它是用 TypeScript 编写的，这是一种我不知道的语言，但它确实解决了我的问题。因此，我将尝试围绕代码进行思考。

编辑：我设法在 Python 中逐行重新编码整个内容。所以现在这对我来说已经解决了

从预先存在的 n-n 关系（如果存在）中找到随机 [0,1]-1 配对的算法

Algorithm to find random [0,1]-1 pairing from a preexisting n-n relationship (if one exists)

algorithm

graph

set

relationship