Ask Your Question
2

How to get the collection of all functions from X to Y in SageMath

asked 2018-12-03 06:36:11 -0600

sagelearner gravatar image

Let $X={1,2,…,n}$ and $Y={1,2,…,m}$. Is there any way to get the set of all functions from $X$ to $Y$ in SageMath?

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
3

answered 2018-12-03 14:21:43 -0600

FrédéricC gravatar image

Like this:

M = FiniteSetMaps(["a", "b"], [3, 4, 5]); M
edit flag offensive delete link more

Comments

Exactly the right tool. To further illustrate:

For $n = 2$, $m = 3$:

sage: M = FiniteSetMaps([1 .. 2], [1 .. 3]); M
Maps from {1, 2} to {1, 2, 3}
sage: for f in M: print(f)
map: 1 -> 1, 2 -> 1
map: 1 -> 1, 2 -> 2
map: 1 -> 1, 2 -> 3
map: 1 -> 2, 2 -> 1
map: 1 -> 2, 2 -> 2
map: 1 -> 2, 2 -> 3
map: 1 -> 3, 2 -> 1
map: 1 -> 3, 2 -> 2
map: 1 -> 3, 2 -> 3

For $n = 3$, $m = 2$

sage: M = FiniteSetMaps([1 .. 3], [1 .. 2]); M
Maps from {1, 2, 3} to {1, 2}
sage: for f in M: print(f)
map: 1 -> 1, 2 -> 1, 3 -> 1
map: 1 -> 1, 2 -> 1, 3 -> 2
map: 1 -> 1, 2 -> 2, 3 -> 1
map: 1 -> 1, 2 -> 2, 3 -> 2
map: 1 -> 2, 2 -> 1, 3 -> 1
map: 1 -> 2, 2 -> 1, 3 -> 2 ...
(more)
slelievre gravatar imageslelievre ( 2018-12-03 15:10:33 -0600 )edit
1

answered 2018-12-03 09:21:10 -0600

Emmanuel Charpentier gravatar image

updated 2018-12-04 01:10:01 -0600

Disclaimer : I know zilch about combinatirics. This problem might have elegant (and already programmed) solutions among the combinatorics tools of Sage. However, the problem seems simple enough to attempt a "naïve" solution.

A function from $X$ to $Y$ is the set of tuples $[ (x_i,y_j),...,i=1,\dots,n,j\in[0..n]]$, meaning that $x_i$ has $y_j$ as image, the notation $(x_i,y_0)$ denoting the case where $x_i$ has no image. Let $S_{n,m}$ the set of all functions from $X$ to $Y$ when X has $n$ elements and Y has $m$ elements.

1): the set $S_{1,m}$ is simply $[(x_1,y_j),j=0,...,m]$.

2): knowing $S_{n,m}$, one can simply build $S_{n+1,m}$ by adding (i. e. concatenating) to each of the functions in $S_{n,m}$ a member of $[(x_{n+1},y_j),j=0,...,m]$. In other words, S_{n+1,m}$ is the cartesian product of $S_{n,m}$ and $[(x_{n+1},y_j),j=0,...,m]$.

3): 1) and 2) are sufficient to build $S_{n,m}$ by recurrence on n. It results immediately that the cardinal is $(m+1)^n$, including the degenerate case where no element of $X$ has an image in $Y$.

The implementation, whose details depend of the planned use of the functions, is, as usual, left to the reader as an exercise ;-).

edit flag offensive delete link more

Comments

Thanks for the theory!

Dox gravatar imageDox ( 2018-12-04 01:34:54 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-12-03 06:36:11 -0600

Seen: 66 times

Last updated: Dec 04