Suggested languages for you:

Americas

Europe

Q24E

Expert-verified
Found in: Page 203

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Describe an algorithm that determines whether a function from a finite set to another finite set is one-to-one.

An algorithm that determines whether a function from a finite set of integers to another finite set of integers is one-to-one, can be given as below:

\user1 procedure one-to-one f ( x ) ($X=\left\{{x}_{1},{x}_{2},...,{x}_{n}\right\},y=\left\{{y}_{1},{y}_{2},....,{y}_{m}\right\}$ : set of integers)

\user1 for $i:=1$ to m

Algorithm will return true if given function is one-to-one function, otherwise, it will return false.

See the step by step solution

## Step 1: Steps Algorithm follows

Steps that algorithm has to follow are:

1. We will use for loop to select element from Y having condition $i=1$ to m . Then, use another for loop to select element from X , having condition J = 1 to n .
2. Then if statement will check that every element in Y has corresponding element in . Condition for if loop will be $f\left({x}_{j}\right)={y}_{i}$ .
3. We use one variable to count how many elements in have corresponding element in . If there is only one corresponding value in X for any element in Y i.e., then algorithm will return true, otherwise it will return false.

## Step 2:

The algorithm based on above conditions given as below:

\ user1 procedure one-to-one f ( x ) ($X=\left\{{x}_{1},{x}_{2},...,{x}_{n}\right\},y=\left\{{y}_{1},{y}_{2},...,{y}_{m}\right\}$ : set of integers)

\ user1 for $i:=1$ to m