从一组成对中生成组合，而无需重复元素

cs.stackexchange https://cs.stackexchange.com/questions/11

  •  16-10-2019
  •  | 
  •  

题

我有一对。每对的形式（x，y），使得x，y属于该范围的整数 [0,n).

因此，如果n是4，那么我有以下对：

(0,1) (0,2) (0,3)
(1,2) (1,3) 
(2,3)

我已经有两对了。现在，我必须使用 n/2 成对使得所有整数都没有重复（换句话说，每个整数在最终组合中至少出现一次）。以下是正确理解的正确组合和错误组合的示例

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

一旦我有两对，有人可以建议我一种生成所有可能组合的方法。

有帮助吗？

解决方案

一种直接的方法是递归过程，在每个调用上执行以下操作。该过程的输入是已经选择的对的列表和所有对的列表。

  1. 计算输入列表尚未涵盖的最小数字。对于第一次调用，当然将是0，因为没有对成对选择。
  2. 如果涵盖了所有数字，则有一个正确的组合，将其打印出来并返回上一步。否则，发现的最小数字是我们目标的目标。
  3. 浏览对成对，寻找一种覆盖目标编号的方法。如果没有，则只需返回前面的递归级别即可。
  4. 如果有一种覆盖目标编号的方法，请选择第一种方式并递归地调用整个过程，而两人刚选择的添加到选定对的列表中。
  5. 返回时，寻找 下一个 用一对覆盖目标编号的方法，而不会重叠以前选择的对。如果找到一个，请选择它，然后再次递归调用下一个过程。
  6. 继续步骤4和5，直到没有更多涵盖目标编号的方法。浏览整个对列表。如果没有正确的选择，请返回递归的先前级别。

可视化该算法的方法是与一棵树的路径是非重叠对的序列。树的第一级包含所有包含0的对的对。对于上面的示例，树是

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

在此示例中，所有穿过树的路径实际上给出了正确的收集，但是例如，如果我们忽略了这对（1,2），那么最右边的路径只有一个节点，并且将与步骤3中的搜索相对应。

可以为列举特定类型的所有对象的许多类似问题开发此类型的搜索算法。

有人建议，也许OP意味着 全部 在输入中，对，不仅仅是一个问题，正如问题所说。在这种情况下，算法要容易得多，因为不再需要检查允许哪个对。甚至没有必要生成所有对的集合；以下伪代码将执行OP要求的事情。在这里$ n $是输入号，“列表”以空列表开始，而“覆盖”是一个长度为$ n $初始化为0的长度。它可以使其更有效，但这不是我的直接目标。 

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}

其他提示

您可以迭代地解决。假设您拥有所有解决方案$ s_n $，范围$ [0，n）$。然后，您可以轻松地从$ s_n $构造解决方案$ s_ {n+2} $。 $ n $的尺寸非常快，因此编写生成器而不是将所有集合保存在内存中可能是一件好事，请参见下面的Python示例。

def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2) 
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

您可以通过打电话列出所有对

for x in pairs(6):
   print(x)

更新: ：我的早期答案涉及双方图形，OP并未询问。我现在将其留在相关信息中。但是，更相关的信息涉及在非面积图中的完美匹配。

在这方面， PROPP进行了一项不错的调查 这概述了进展（直到1999年）。该文章中的一些想法以及相关的链接可能被证明是有用的。 tl; dr是 - 很棘手:)

---旧答案的开始

请注意，您要做的就是列举所有可能的完美匹配，这是在两部分图上列举的。这样做有许多不同的算法，特别是最近的算法是 艾萨克2001.

基本思想是通过使用网络流量找到一个完美的匹配，然后通过交替的周期重复修改它（有关更多信息，请参见网络流的任何算法教科书章节）。

您选择的每对都消除了您无法从中选择的两行。这个想法可用于设置递归算法（在Scala中）：

def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

当然，这可以更有效地表达。特别是，不必考虑整个行以进行组合的想法。 filter.

虽然这个问题已经有很多可爱的Ansewers，但我认为指出他们背后的基本，一般的窍门会很高兴。

如果您可以完全订购要组合的元素，那么生成唯一组合要容易得多. 。这样，只要我们允许排序的组合，就可以保证唯一性。也不困难地生成分类的组合 - 只需进行通常的蛮力枚举搜索，但是在每个步骤中，选择元素都比已经在每个步骤中选择的元素更大。

这个特定问题的额外并发症是只想获得长度N/2（最大长度）的组合。如果我们决定制定良好的分类策略，这并不难。例如，正如卡尔·木乃伊（Carl Mummet最小的仍然未使用的数字。

如果要生成其他长度的序列，我们还可以扩展此策略。请记住，每当我们选择下一个元素的第一个数字不是最小的元素时，我们就排除了一行或多个元素，从出现在排序子序列上的一行，因此，PRERMUNT的最大长度会相应地减少。

我不确定这是否是您要问的，但是据我了解，您有所有$ n 选择2美元的$ [n] = {1， cdots，n } $的2 $无序对，并想计数列表在覆盖集合$ [n] $的所有对中，其中$ n $是一个偶数号码。我们可以将其视为 边缘覆盖 $ k_n $，$ n $顶点的完整图。

此外，这个问题似乎假设$ [n] $中的每个数字仅在列表中出现一次。在这种情况下，我们只是在看覆盖物 完美匹配. 。图中的匹配数等于 永恒的 它的 邻接矩阵. 。因此，我们需要计算$ mathsf {perm}（k_n）$。

众所周知，永久是 $ MATHSF {＃P text { - }完整} $ , ，但这是通常的。对于$ k_n $，有$ frac {n！} {2^{ frac {n} {2}}}} $此类列表。

生成所有这些的最简单方法是修复一个完美的匹配，然后应用$ [n] $的排列，但这将产生许多重复。

许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top