Determine if a function is bijective

Question

Concise Problem Specification

Given an integer \$n\$ and a function \$f : X \to X \$ where \$X = \{1,2,3,..,n\}\$ Determine whether the given function is a bijective function or not.

Definition:

According to Wikipedia:

In mathematics, a bijection, bijective function or one-to-one correspondence is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

Constraints

\$1\le n \le 20 \$

Input format

There are lines in the input. The first line contains a single positive integer \$n\$.
The second line contains space separated integers, the values of \$f(1)\$ , \$f(2)\$ ... , \$f(n)\$, respectively.

Output Format

On a single line, output "YES" if is bijective. Otherwise, output "NO".

Solution

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        Set<Integer> codomain = new HashSet<Integer>();

        for (int i = 0; i < n; i++) {
            int y = in.nextInt();
            codomain.add(y);
        }

        System.out.println(codomain.size() == n ? "YES" : "NO");

        in.close();

    }

}

Comments

I am still relatively new to Java and would appreciate any comments on the above regarding improvements to my code.

Answer 1

Your code looks nice. The only suggestion I have is to separate the bijection check out of the main, and make it, say, a static method. All in all, I had this in mind:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class FunctionUtils {

    public static boolean isBijection(final Map<Integer, Integer> function) {
        final Set<Integer> domain = new HashSet<>(function.keySet());
        final Set<Integer> range  = new HashSet<>(function.values());
        return range.equals(domain);
    }

    public static void main(String[] args) {
        final Map<Integer, Integer> function = new HashMap<>();

        try (final Scanner in = new Scanner(System.in)) {
            final int n = in.nextInt();

            for (int i = 1; i <= n; i++) {
                function.put(i, in.nextInt());
            }

            System.out.println("Bijection: " + isBijection(function));
        }
    }
}

Hope that helps.

Edit

Validating general bijections \$f \colon X \to Y\$ is not any harder:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

public class FunctionUtils {

    public static <E> boolean isBijection(final Map<E, E> function) {
        return function.size() == new HashSet<>(function.values()).size();
    }

    public static void main(String[] args) {
        final Map<Integer, Integer> function = new HashMap<>();

        try (final Scanner in = new Scanner(System.in)) {
            final int n = in.nextInt();

            for (int i = 1; i <= n; i++) {
                function.put(i, in.nextInt());
            }

            System.out.println("Function:  " + function);
            System.out.println("Bijection: " + isBijection(function));
        }
    }
}

Answer 2

Defensive programming please.

You've only verified that the function is injective, but you didn't test for surjective property.

That means that codomain.size() == n only tells you that every \$f(x)\$ was unique. However, you probably should also have validated that all of the given \$f(1),f(2),...,f(n)\$ where also within the permitted range of \$[1,n]\$

While the specified function signature doesn't even allow this case (so the corresponding test would pass trivially), this becomes relevant if you were to reuse the logic in an environment where this guarantee isn't given.

Well, actually you didn't even test the injective property properly. You only checked if \$n\$ unique values where found in the input. Not if there were also exactly \$n\$ inputs provided.

Currently, your program would wrongly judge the following example as bijective, despite not even being a valid input by any means:

4
20 21 22 23 20 20 20

Answer 3

It looks like your strategy is to check whether the n values are all distinct. You could tighten up the code slightly by noticing the return value of Set.add():

Returns:

true if this set did not already contain the specified element

So, print "NO" if any of the .add() operations returns false.