user0000 user0000 - 5 months ago 13
Python Question

How to generate all injective functions with specified domain and range?

I am a (very) beginner programmer, and especially new at Python.

I want to take a specified domain and a specific range and generate injective maps. For example, I could have the domain be A = [1, 2] and the range be B = [1, 3] and I would like the output to look something like "(1 -> 1, 2 ->3 ), (1 -> 3, 2 -> 1)". Or something like ((1,1),(2,3)) and ((1,3),(2,1)) would be fine.

As another example, I could take A = [2, 3] and B = [1, 2] and I would want "(2 -> 1, 3 -> 2), (2 -> 2, 3 -> 1)".

My best attempt is

A = [1, 2]
B = [1, 3]
C = []
for x in A:
for y in B:
C.append((x, y))


which produces the list [(1, 1), (1, 3), (2, 1), (2, 3)]. I understand why it produces that, but I can't think of any way to actually produce what I want.

I would prefer a solution using basic Python tools, like loops, lists, sets, etc.

Answer

Permute one of the two lists (from itertools import permutations), and for each of the permutations do a one-to-one mapping (zip(..)).

>>> from itertools import permutations
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> [zip(a, x) for x in permutations(b)]
[[(1, 4), (2, 5), (3, 6)], [(1, 4), (2, 6), (3, 5)], [(1, 5), (2, 4), (3, 6)], [(1, 5), (2, 6), (3, 4)], [(1, 6), (2, 4), (3, 5)], [(1, 6), (2, 5), (3, 4)]]

Running it for your example:

>>> a = [1,2]
>>> b = [1,3]
>>> [zip(a, x) for x in permutations(b)]
[[(1, 1), (2, 3)], [(1, 3), (2, 1)]]
Comments