# Surjective, Injective, Bijective, or Nothing?

Given a mapping from the integers from 1 to N to the integers from 1 to N, determine if the mapping is surjective, injective, bijective, or nothing.

You may choose any character/digit for the four outputs.

# Specs

Input format: n, arrays of pairs (n is the highest number in the domain and range)

For example, if the first number is 3, then both the domain and the co-domain are {1,2,3}.

For example, {i+1 | i from 1 to 9} (n=10) is represented by 10, [[1,2],[2,3],...,[9,10]].

The input may contain duplicate.

# Testcases

2, [[1,2],[2,1]] => bijective
2, [[1,1],[1,2]] => surjective
3, [[1,1]] => injective
3, [[1,2],[2,3]] => injective
4, [[1,2],[2,2],[3,2],[4,2]] => nothing
2, [[1,2],[1,2]] => injective
3, [[1,1],[1,2],[1,3]] => surjective
2, [[1,1],[1,1],[2,2]] => bijective

• Some languages don't have arrays of pairs. Can the input be more flexible? Like two arrays for functions' domain and codomain? May 25, 2016 at 23:53
• What's the desired result for 2, [[1,1],[1,2],[2,2]]?
– Neil
May 25, 2016 at 23:56
• ^^yes, ^nothing May 25, 2016 at 23:59
• Do the mappings need to be functions to qualify as bi/in/surjections? May 26, 2016 at 0:01
• Why is 4 surjective when the result is only ever 2? Is the mapping really from {1,...,N} to {1,...,N}? May 26, 2016 at 3:10

# Pyth - 109 13 bytes

im&{IdqSQSdE2


Takes domain and codomain separately as allowed by comments in OP.

• It does not work... May 26, 2016 at 0:06
• @LeakyNun, but, but it gives the right answers? May 26, 2016 at 0:07
• You did not account for duplicates May 26, 2016 at 0:12
• @LeakyNun what about now? May 26, 2016 at 0:14
• Looks like I've confused the definition of surjectivity... consider changing your answer? May 26, 2016 at 4:36

# Pyth, 15 bytes

+!-SQJeC{E*2{IJ


The output is identified by:

nothing   : 0
surjective: 1
injective : 2
bijective : 3


In pseudocode,

                  Q=input()                 # pre-initialized var, 'n'
+                 sum(                      # sur=1,in=2,thus bi=sur+in=3,no=0
!                  not(                    # if 'filtrate'=[], true/surjective
-SQ                 filter(range(1,Q),    # filter codomain by range
JeC{E              J=transpose(deduplicate(input()))[-1]
))  # find the "redundant" range, may corrspnd to diffrnt args
*2{IJ              2*invariant(J,deduplicate)
) # if J(redundnt range) invariant undr dduplicatn, true/injectiv


Test suite

Currently, the test suite returns two False's, namely for case 2 and case -2 (second-to-last). This has to do with the definition of "injective", and will be discussed with the OP.

# Python, 85 82 bytes

The methodology here is basically:

• Remove duplicate points
• Check if the cardinality of the image of the domain + cardinality of domain is equal to twice the number of points
• If true -> injective -> return 1
• Check if the cardinality of the image of the domain is equal to the cardinality of the codomain
• If true -> surjective -> return 2
• If both true -> bijective -> return 3
• If neither -> nothing -> return 0
def f(n,t):l=len;d,c=zip(*set(t));x=l(set(c));return(x+l(set(d))==l(c)*2)+(x==n)*2


## Test Cases

print(f(2, [(1,2),(2,1)])==3)# => bijective
print(f(2, [(1,1),(1,2)])==2)# => surjective
print(f(3, [(1,1)])==1)# => injective
print(f(3, [(1,2),(2,3)])==1)# => injective
print(f(4, [(1,2),(2,2),(3,2),(4,2)])==0)# => nothing
print(f(2, [(1,2),(1,2)])==1)# => injective
print(f(3, [(1,1),(1,2),(1,3)])==2)# => surjective
print(f(2, [(1,1),(1,1),(2,2)])==3)# => bijective


Update