arrays - 找到两个集合之间所有可能的双射

Question

我想做的是创建一个算法，能够找到两组对象之间所有可能的双射。

一个简单的例子，假设我们有两个数组{1,2,3} {4,5,6}。

算法应该给我 3!= 3*2*1 =6 个双射，它们如下:

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\

尽管一开始看起来很简单，但我还是很困惑。组合数学、双射或排列理论中有没有什么标准算法可以解决这个问题？先感谢您。

克里斯蒂娜

Answer 1

您应该递归执行此操作，从每个变量中“选择”一个变量 - 并将其添加到解决方案中 - 针对所有可能性执行此操作，并在每次递归调用时缩小可能的选择范围。

伪代码应该类似于[假设 |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

请注意，它确实产生了 n! 种可能性，因为每次迭代都少了一个可供选择的元素，因此总共有 n * (n -1) * ... * 1 = n! 可能性，正如预期的那样..