确定从有限集 A 到有限集 B 的函数 f 是否为本体函数的算法。

Question

我如何编写一个算法来确定从有限集 A 到有限集 B 的函数 f 是否是一个本体函数。

这是我目前拥有的：

A: array ( members of set A )
B: array ( members of set B )

Mapped: associative array of Boolean variables.

for each b in B:

Mapped[b] = false


for each a in A:

Mapped[f(a)] = true


Onto = true;

for each b in B:

Onto = Onto AND Mapped[b]


return Onto

这是正确的吗？

Answer 1

是的，那行得通。一个可能更简单的方法是

for each a in A:
    remove f(a) from B
return (is B empty?)

当然你应该先排序B，这样你可以更快地删除。

确定从有限集 A 到有限集 B 的函数 f 是否为本体函数的算法。

An algorithm that determines if a function f from the finite set A to the finite set B is an onto function.

discrete-mathematics