问查找两个集合之间的所有可能的双射

EN

你应该递归地选择，从每个变量中“选择”一个变量，并将其添加到解决方案中-尽可能地这样做，并在每次递归调用时缩小可能的选择范围。()

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

请注意，it确实会生成 n! possibilities，，因为每次迭代都会少一个元素可供选择，这导致了所有的n * (n-1) * ... * 1 = n!可能性，正如预期的那样。

在组合学，双射或排列理论中有没有标准的算法来解决这个问题？

是的！生成N个元素的两个集合之间的所有双射与生成N个元素的所有排列相同；可以将该排列看作是，对于第一个集合中的每个元素，第二个集合中的哪个元素将是该双射下的图像。因此，您正在寻找一种“生成所有排列”的算法。

Knuth有一个关于这个主题的简短book，你也可以免费下载："The Art of Computer Programming: Generating all Permutations“(注:压缩postscript格式)。他给出的第一个算法是“算法L"，这是一个明显的递归算法的有趣替代方案。

你可能会对维基百科上关于"Algorithms to generate permutations“的讨论感兴趣。如果您使用C++编程，则可以在next_permutation函数中使用该实现。

(当然，这假设您谈论的是可数集，而不是像x ⟼ x+1这样的实数的双射。)

简化这个问题的一种方法是简单地获取第二阵列的所有排列，然后在第一阵列和每个排列的第二阵列之间执行n到n映射。

例如，如果你有1,2和3,4，首先计算3,4 -> {3,4,4,3}的排列，然后将每个排列配对为1,2，结果是{(1,3)，(2,4)，(1,4)，(2,3)}。

我已经在下面的Python中包含了一个示例实现。

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)]