有限集合Aから有限集合Bまでの関数fが関数onであるかどうかを決定するアルゴリズム。

Question

有限集合Aから有限集合Bまでの関数fが関数onであるかどうかを決定するアルゴリズムを書くにはどうしたらいいですか？

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が最初に並べ替える必要があるので、あなたはより迅速に削除することができます。