5
\$\begingroup\$

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.

\$\endgroup\$
0

3 Answers 3

4
\$\begingroup\$

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));
        }
    }
}
\$\endgroup\$
9
  • \$\begingroup\$ range.equals(domain) checks that the function's outputs are a permutation of its inputs, which is a stricter condition than being a bijection. The helper function would therefore be better named isPermutation(). \$\endgroup\$ Jun 20, 2016 at 19:34
  • \$\begingroup\$ Yes, but, please, note that OP mentioned \$f \colon X \to X\$. \$\endgroup\$
    – coderodde
    Jun 20, 2016 at 19:43
  • \$\begingroup\$ Given that function.keySet() is already a Set<Integer>, there's no real benefit to copying it into a HashSet<Integer>. There's also no real downside to genericising the test: nothing in isBijection truly relies on the types of the domain and range being Integer. \$\endgroup\$ Jun 21, 2016 at 7:39
  • 1
    \$\begingroup\$ @PeterTaylor I was reworking my answer while you brought the Set issue. Now there is only one HashSet involved. \$\endgroup\$
    – coderodde
    Jun 21, 2016 at 7:43
  • 1
    \$\begingroup\$ I would have gone one step further and made it public static <D, C> boolean isBijection(final Map<D, C> function), but +1 anyway. \$\endgroup\$ Jun 21, 2016 at 7:47
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.