Bijection

• 04-22-2012, 10:00 AM
qato
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, 10:56 AM
pbrockway2
Re: Bijection
Quote:

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.
This is a bit confusing. If A and B are 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, 11:34 AM
qato
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, 11:48 AM
pbrockway2
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".