Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By pbrockway2

Thread: Bijection

  1. #1
    qato is offline Member
    Join Date
    Apr 2012
    Posts
    2
    Rep Power
    0

    Default 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

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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.
    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).

  3. #3
    qato is offline Member
    Join Date
    Apr 2012
    Posts
    2
    Rep Power
    0

    Default 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

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default 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".
    DarrylBurke likes this.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •