# Assistance needed!

• Apr 24th 2013, 02:44 PM
rtrumpow
Assistance needed!
Hello;

I am posed with this question. I have researched the internet for instruction but I see the same canned answer. Can someone help me on this question? I do not know where/how to begin:

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

This is what I have found:
initialize empty set C
for all x in A:
C = the union of C and {f(x)}

for all y in B:
if y is not a member of C, return NOT_ONTO

return ONTO
Is there another way to answer the question?
• Apr 24th 2013, 08:50 PM
chiro
Re: Assistance needed!
Hey rtrumpow.

You could initialize a 1-D array that is the size of the set B and iterate through all elements in A and increment array[f(x)] by 1 where x is an element of A.

In other words

array = new int[SizeOfSetB];
InitializeArrayToAllZeros(array);

for (x = 1 to SizeOfSetA)
{
elementOfA = SetA[x];
array[function(elementOfA)]++;
}

onto = true;
for (i = 1 to SizeOfSetB)
{
if (array[i] == 0)
{
onto = false;
break;
}
}

// onto contains status of onto.