查找两组之间的所有可能的双射

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

一个简单的例子，假设我们有两个数组{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 \

即使起初看起来很简单，我很困难。在组合，双射或排列理论中是否有任何标准算法来解决这个问题？预先感谢您。

克里斯蒂娜

来源

2012-02-11 Xristina

你应该这样做递归“选择”从每一个变量 - 它添加到解决方案 - 做到这一点对所有的可能性，并在每个递归调用缩小可能的选择。

伪代码应该是类似于[假设| 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!可能性，如预期..

少了一个元素

来源

2012-02-11 19:16:21 amit

在组合，双射或排列理论中是否有任何标准算法来解决这个问题？

是的！生成两组N元素之间的所有双射与相同，生成N个元素的所有排列;将排列考虑为第一组的每个元素指示第二组中的哪个元素将是双射下的图像。因此，您正在寻找一种算法来“生成所有排列”。关于这个问题，Knuth有一个简短的book，你也可以免费下载：“The Art of Computer Programming: Generating all Permutations”（注意：压缩的postscript格式）。他给出的第一个算法是“算法L”，这是一个有趣的替代明显的递归算法。

关于“Algorithms to generate permutations”的维基百科讨论将引起您的兴趣。如果您使用C++编程，则可以使用next_permutation函数中的实现。

（当然，这是假设你是在谈论可数套，而不是，比方说，实数的双射，如x ⟼ x+1）

来源

2012-02-11 19:17:16 nibot

我想你想写“有限”而不是“可数”？ – 2012-02-11 20:14:08

我认为可以列出像整数这样的无限可数集合的排列。 – nibot 2012-02-11 21:00:24

如果你可以列出一个不可数集，是的：[一个简单的双数对自然数的不可数性证明？]（http://mathoverflow.net/questions/29475/an-easy-proof-of-the-uncountability-自然数的双射） – 2012-02-11 21:13:45

来简化这个问题是简单地采取所有排列的一种方式然后在第一阵列和每个排列的第二阵列之间执行n对n的映射。例如，如果您有[1,2]和[3,4]，首先计算[3,4] - > {[3,4]，[4,3]}的置换，然后计算[3,4,4]每对配对[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)]

来源

2012-02-11 19:20:38 cheeken

查找两组之间的所有可能的双射

回答

相关问题