Блог

Главная - Вопросы по программированию - Алгоритм, который определяет, является ли функция f из конечного множества A в конечное множество B функцией onto.

Алгоритм, который определяет, является ли функция f из конечного множества A в конечное множество B функцией onto.

#discrete-mathematics

#дискретная математика

Вопрос:

Как я могу написать алгоритм, который определяет, является ли функция f из конечного множества A в конечное множество B функцией onto.

Это то, что у меня есть на данный момент: 

 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

Это правильно?

Комментарии:

1. На мой взгляд, выглядит неплохо. Вы получаете A.

2. Ha ha! Спасибо, профессор!

Ответ №1:

Да, это сработает. Потенциально более простым подходом было бы

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

И тогда, конечно, сначала вам следует отсортировать B , чтобы быстрее удалять.