Results 1 to 4 of 4

- 04-22-2012, 09:00 AM #1Member
- Join Date
- Apr 2012
- Posts
- 2

- Rep Power
- 0

## Bijection

Hi,

I have two sets let's say A={a,b,c} and B={x,y,z}. I need to get all possible "bijections" between them. For example {(a:x), (b:y), (c,z)}, {(a:x), (b:z), (c,y)}, {(a:y), (b:x), (c,z)}, etc. I know it is a filtered combination of 3 from the product set of A and B however when it comes to filtering i'm a bit stuck where in my case, a might be equal to b or c.

Any idea or help would be appreciated

Thank you

- 04-22-2012, 09:56 AM #2Moderator
- Join Date
- Feb 2009
- Location
- New Zealand
- Posts
- 4,712

- Rep Power
- 14

## Re: Bijection

I have two sets let's say A={a,b,c} and B={x,y,z}. ... i'm a bit stuck where in my case, a might be equal to b or c.**sets**then a cannot be equal to b or c. If A and B are not sets but something else, could you clarify?

Assuming they are sets... then they have the same number of elements. (otherwise obtaining the set of bijections is easy!) Conceptually we can ignore A and concentrate on B. Taking the elements of A in some arbitrary (but fixed) order the corresponding elements of B will be some permutation of its elements. Each permutation gives rise to a distinct bijection, and each bijection gives rise to a distinct permutation. So, basically the problem in this case reduces to finding all the permutations of n elements (where the cardinality of the sets involved is n).

- 04-22-2012, 10:34 AM #3Member
- Join Date
- Apr 2012
- Posts
- 2

- Rep Power
- 0

## Re: Bijection

Thank you for straightening things up. Yes you re right they are not sets but still, in my case, they have the same number of elements so using permutations on B should work. Thank you

- 04-22-2012, 10:48 AM #4Moderator
- Join Date
- Feb 2009
- Location
- New Zealand
- Posts
- 4,712

- Rep Power
- 14

## Re: Bijection

You might want to check out Narayana Pandita's classic 14th century algorithm: it produces the permutations in lexicographic order and copes with "multisets".

## Bookmarks