我想做的是创建一个算法,能够找到两组对象之间所有可能的双射。
一个简单的例子,假设我们有两个数组{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\
尽管一开始看起来很简单,但我还是很困惑。组合数学、双射或排列理论中有没有什么标准算法可以解决这个问题? 先感谢您。
克里斯蒂娜
最佳答案
您应该递归执行此操作,从每个变量中“选择”一个变量 - 并将其添加到解决方案中 - 针对所有可能性执行此操作,并在每次递归调用时缩小可能的选择范围。
伪代码应该类似于[假设 |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!
可能性,正如预期的那样..
关于arrays - 找到两个集合之间所有可能的双射,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9243198/