Search for all possible bijections between two sets

Question

what I want to do is create an algorithm that can find all possible bijections between two sets of objects.

A simple example, let's say we have two arrays {1,2,3} {4,5,6}.

The algorithm should give me 3! = 3 * 2 * 1 = 6 bijections, which are as follows:

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-5 3-4 \ 1-6 2-4 3-5 \

Despite the fact that it seems simple in the first place, I'm pretty stuck. Is there a standard algorithm in the theory of combinatorics, bijections, or permutations to solve this problem? Thanks in advance.

Christina

Answer 1

You have to do it recursively , "select" one variable from each "and add it to the solution - do it for all possibilities and limit the options for each recursive call.

The pseudocode should be something like [provided | S1 | == | S2 |]:

getAllBijections(S1,S2,sol): if (S1 is empty): print sol else: first <- S1.first S1 <- S1.deleteFirst() for each e in S2: S2.remove(e) sol.append(first,e) getAllBijections(S1,S2,sol) // note we are invoking with modified S1,S2,sol sol.removeLast() //remove the last sol S2.add(e) //return e to S2 end for end if 

Note that it does generate n! possibilities , because for each iteration you have one less element to choose from, resulting in n * (n-1) * ... * 1 = n! opportunities as expected.

Answer 2

Is there any standard algorithm in the theory of combinatorics, bijections, or permutations to solve this problem?

Yes! . The generation of all bijections between two sets of N elements is the same as the creation of all permutations of N elements; think of a permutation as indicating for each element of the first set which element of the second set will be the image under the bijection. So you are looking for an algorithm to “generate all permutations”.

Knut has a short book on a topic that you can also download for free: “The Art of Computer Programming: Creating All Permutations ” (note: a compressed postscript format). The first algorithm he gives is Algorithm L, an interesting alternative to obvious recursive algorithms.

The Wikipedia discussion " Permutation Generation Algorithms " will be of interest to you. If you program in C ++, you can use the implementation in next_permutation .

(Of course, this assumes that you are talking about countable sets, and not, say, bijections of real numbers, such as x ⟼ x+1 )

Answer 3

A way to simplify this problem is to simply take all the permutations of the second array and then perform an n-to-n mapping between the first array and each second permuted array.

For example, if you have [1,2] and [3,4], first compute the permutations [3,4] → {[3,4], [4,3]}, and then pair each to [1,2 ]. As a result, we obtain {[((1,3), (2,4)], [(1,4), (2,3)]}.

I have included an example implementation in Python below.

 import itertools a = [1,2] b = [3,4] for p in itertools.permutations(b): print zip(a,p) # Output: # [(1, 3), (2, 4)] # [(1, 4), (2, 3)]