7
\$\begingroup\$

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

3 Answers 3

1
\$\begingroup\$

Pyth - 10 9 13 bytes

im&{IdqSQSdE2

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

Test Suite.

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

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.

\$\endgroup\$
0
\$\begingroup\$

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

  • -3 [16-05-26] Multiplied by 2 instead of adding
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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