计算多个列表中项目对的组合而不重复

Question

假设我们有多个项目对列表，例如：

1. {12,13,14,23,24}
2. {14,15,25}
3. {16,17,25,26,36}

其中 12 是一对项目“1”和“2”（因此 21 相当于 12），我们想要计算可以从每个列表中选择项目对的方式数量，这样就没有单一项目重复。 您必须从每个列表中选择一对，并且只能选择一对。 每个列表中的项目数和列表数是任意的，但您可以假设至少有两个列表，每个列表至少有一对项目。 这些对由有限字母表中的符号组成，假设为数字 [1-9]。 此外，列表既不能包含重复的对 {12,12} 或 {12,21}，也不能包含对称对 {11}。

更具体地说，在上面的示例中，如果我们从第一个列表中选择一对项目 14，那么我们对第二个列表的唯一选择就是 25，因为 14 和 15 包含“1”。 因此，第三个列表中的唯一选择是 36，因为 16 和 17 包含“1”，而 25 和 26 包含“2”。

有谁知道一种有效的方法来计算项目对的总组合，而无需遍历每个选择排列并询问“这是一个有效的选择吗？”，因为每个列表可以包含数百个对的物品？

---

更新

在花了一些时间之后，我意识到当没有一个列表共享不同的对时，计算组合的数量是微不足道的。 然而，一旦两个或多个列表之间共享不同的对，组合公式就不适用。

到目前为止，我一直在试图弄清楚是否有一种方法（使用组合数学而不是暴力）来计算每个列表具有相同项目对的组合数量。 例如：

1. {12,23,34,45,67}
2. {12,23,34,45,67}
3. {12,23,34,45,67}

Answer 1

问题是#P-完整的。 这比 NP 完全问题更难。 这就像找到 SAT 考试中满意的作业数量一样困难。

减少来自完美匹配。 假设您有图 G = {V, E}，其中 E（边集）是顶点对列表（由边连接的顶点对） ）。 然后通过使用 E 的 |V|/2 副本对“项目对”的实例进行编码。 换句话说，E 的副本数量等于顶点数量的一半。 现在，您的情况中的“命中”将对应于没有重复顶点的 |V|/2 边，这意味着所有 |V| 顶点都被覆盖。 这就是完美匹配的定义。 每一次完美的匹配都会很成功——这是一一对应的。

Answer 2

可以说列表中的每个元素都是图中的一个节点。 如果两个节点可以一起选择，则它们之间有一条边（它们没有公共符号）。 同一列表的两个节点之间没有边。 如果我们有 n 个列表，问题就是找到图中大小为 n 的派系的数量。 不存在大于 n 个元素的团。 鉴于找出至少一个这样的派系是否存在是 np 完全的，我认为这个问题是 np 完全的。 请参阅：http://en.wikipedia.org/wiki/Clique_problem

正如所指出的，我们有证明解决这个问题可以解决Clique问题，证明这是NP完全的。 如果我们可以计算所需集合的数量，即 n 大小的派系的数量，那么我们就知道是否至少存在一个大小为 n 的派系。 不幸的是，如果没有大小为 n 的派系，那么我们不知道是否存在大小为 k < 的派系。 名词

另一个问题是我们是否可以表示这个问题中的任何图。 我想是的，但我不确定。

我仍然觉得这是 NP 完全的

Answer 3

虽然问题看起来很简单，但它可能与 NP 完全设置覆盖问题有关。 因此，可能没有有效的方法来检测有效组合，因此也没有有效的方法来计算它们。

更新

我认为列表项是成对的，因为这似乎使问题更难攻击 - 您必须检查一项的两个属性。 所以我寻找一种方法将对减少为标量项并找到了一种方法。

将 n 个符号的集合映射到前 n 个素数的集合 - 我将调用此函数 M。 对于符号 0 到 9 的情况，我们获得以下映射，例如 M(4) = 11。

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} => {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

现在我们可以使用映射 X 将一对 (n, m) 映射到 n 和 m 映射的乘积。 这会将 (2, 5) 对转换为 X((2, 5)) = M(2) * M(5) = 5 * 13 = 65。

X((n, m)) = M(n) * M(m)

为什么这一切？ 如果我们有来自两个列表的两对 (a, b) 和 (c, d)，请使用映射 X 将它们映射到 x 和 y 相乘，我们得到乘积 x * y = M(a) * M(b) * M(c) * M(d)< /code> - 四个素数的乘积。 如果我们有 w 列表，我们可以通过从每个列表中选择一对来扩展乘积，并获得 2w 个素数的乘积。 最后一个问题是，这个乘积告诉我们关于我们选择和相乘的对的什么信息？ 如果所选对形成有效选择，我们永远不会选择一个符号两次，因此该乘积不包含两次质数，并且是 广场免费。 如果选择无效，则乘积至少包含两次素数并且不是无平方的。 这是最后一个例子。

X((2, 5)) = 5 * 13 = 65
X((3, 6)) = 7 * 17 = 119
X((3, 4)) = 7 * 11 = 77

选择 25 和 36 得到 65 * 119 = 7735 = 5 * 7 * 13 * 17 并且是无平方的，因此有效。 选择 36 和 34 得到 119 * 77 = 9163 = 7² * 11 * 17 并且不是无平方的，因此无效。

另请注意，这很好地保留了对称性 - X((m, n)) = X((n, m)) - 并禁止对称对，因为 X((m, m)) = M(m) * M (m) 不是无平方的。

我不知道这是否有任何帮助，但现在您知道了并且可以思考它...^^

---

这是将 3-SAT 问题简化为该问题的第一部分。 3-SET 问题如下。

(!A | B | C) & (B | !C | !D) & (A | !B)

这是我所得到的减少量。

• mn 代表一对，
• 一条线代表一个列表，
• 一个星号代表一个任意唯一符号

---

A1-A1'    !A1-!A1'     => Select A true or false
B1-B1'    !B1-!B1'     => Select B true or false
C1-C1'    !C1-!C1'     => Select C true or false
D1-D1'    !D1-!D1'     => Select D true or false

A1-*   !B1-*   !C1-*   => !A | B | C

A2-!A1'   !A2-A1'      => Create a copy of A
B2-!B1'   !B2-B1'      => Create a copy of B
C2-!C1'   !C2-C1'      => Create a copy of C
D2-!D1'   !D2-D1'      => Create a copy of D

!B2-*  C2-*    D2-*    => B | !C | !D

(How to perform a second copy of the four variables???)

!A3-*  B3-*

如果我（或其他人）可以完成这个简化并展示如何在一般情况下做到这一点，这将证明问题是 NP 完全的。 我只是坚持第二次复制变量。

Answer 4

我想说的是，除了蛮力之外，你没有其他计算可以做，因为必须评估一个函数来决定是否可以使用集合 B 中的某个项目（给定集合 A 中选择的项目）。简单的组合数学不会工作。

您可以使用记忆和散列将计算速度加快 1 到 2 个数量级。

记忆是记住类似暴力路径的先前结果。 如果您在列表 n 中并且已经使用了符号 x、y、z，并且之前遇到过这种情况，那么您将从剩余列表中添加相同数量的可能组合。 如何使用 x,y,z 列出 n 并不重要。 因此，如果有缓存结果，请使用缓存结果，或者继续计算到下一个列表并检查那里。 如果您使用强力递归算法来计算结果，但缓存结果，则效果很好。

保存结果的关键是：当前列表，以及已经使用过的符号。 对符号进行排序以制作你的钥匙。 我认为字典或字典数组在这里是有意义的。

使用散列来减少每个列表中需要搜索的对的数量。 对于每个列表，在已经消耗了一定数量的符号的情况下，对可用的对进行哈希。 根据您想要使用的内存量以及您想要花费的预计算时间，选择您想要在哈希中使用的已消耗符号的数量。 我认为使用 1-2 个符号会很好。 按这些哈希值中的项目数对这些哈希值进行升序排序，然后保留前 n 个。 我说扔掉其余的，因为如果哈希值只减少了你的少量工作，那么它可能不值得保留（如果哈希值更多，则需要更长的时间才能找到哈希值）。 因此，当您浏览列表时，您可以快速扫描列表的散列以查看散列中是否使用了符号。 如果有，则使用出现的第一个哈希来扫描列表。 第一个哈希将包含要扫描的最少对。 如果您真的很方便，您也许可以随时构建这些哈希值，而不必预先浪费时间。

您也许可以扔掉散列并使用树，但我的猜测是填充树将需要很长时间。

Answer 5

如果您想生成所有组合，约束编程是一个不错的方法。 为了尝试一下，我使用 Gecode （版本 3.2.2）编写了一个模型来解决您的问题。 给出的两个例子很容易解决，但其他例子可能更难。 无论如何，它应该比生成和测试更好。

/*
 *  Main authors:
 *     Mikael Zayenz Lagerkvist <[email protected]>
 *
 *  Copyright:
 *     Mikael Zayenz Lagerkvist, 2009
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>

using namespace Gecode;

namespace {
  /// List of specifications
  extern const int* specs[];
  /// Number of specifications
  extern const unsigned int n_specs;
}


/**
 * \brief Selecting pairs
 *
 * Given a set of lists of pairs of values, select a pair from each
 * list so that no value is selected more than once.
 *
 */
class SelectPairs : public Script {
protected:
  /// Specification
  const int* spec;
  /// The values from all selected pairs
  IntVarArray s;
public:
  /// The actual problem
  SelectPairs(const SizeOptions& opt)
    : spec(specs[opt.size()]),
      s(*this,spec[0] * 2,Int::Limits::min, Int::Limits::max) {

    int pos = 1; // Position read from spec
    // For all lists
    for (int i = 0; i < spec[0]; ++i) {
      int npairs = spec[pos++];
      // Construct TupleSet for pairs from list i
      TupleSet ts;
      for (int p = 0; p < npairs; ++p) {
        IntArgs tuple(2);
        tuple[0] = spec[pos++];
        tuple[1] = spec[pos++];
        ts.add(tuple);
      }
      ts.finalize();

      // <s[2i],s[2i+1]> must be from list i
      IntVarArgs pair(2);
      pair[0] = s[2*i]; pair[1] = s[2*i + 1];
      extensional(*this, pair, ts);
    }

    // All values must be pairwise distinct
    distinct(*this, s, opt.icl());

    // Select values for the variables
    branch(*this, s, INT_VAR_SIZE_MIN, INT_VAL_MIN);
  }

  /// Constructor for cloning \a s
  SelectPairs(bool share, SelectPairs& sp) 
    : Script(share,sp), spec(sp.spec) {
    s.update(*this, share, sp.s);
  }

  /// Perform copying during cloning
  virtual Space*
  copy(bool share) {
    return new SelectPairs(share,*this);
  }

  /// Print solution
  virtual void
  print(std::ostream& os) const {
    os << "\t";
    for (int i = 0; i < spec[0]; ++i) {
      os << "(" << s[2*i] << "," << s[2*i+1] << ") ";
      if ((i+1) % 10 == 0)
        os << std::endl << "\t";
    }
    if (spec[0] % 10)
      os << std::endl;
  }
};

/** \brief Main-function
 *  \relates SelectPairs
 */
int
main(int argc, char* argv[]) {
  SizeOptions opt("SelectPairs");
  opt.iterations(500);
  opt.size(0);
  opt.parse(argc,argv);
  if (opt.size() >= n_specs) {
    std::cerr << "Error: size must be between 0 and "
              << n_specs-1 << std::endl;
    return 1;
  }
  Script::run<SelectPairs,DFS,SizeOptions>(opt);
  return 0;
}

namespace {
  const int s0[] = {
    // Number of lists
    3,
    // Lists (number of pairs, pair0, pair1, ...)
    5,  1,2,  1,3,  1,4,  2,3,  2,4,
    3,  1,4,  1,5,  2,5,
    5,  1,6,  1,7,  2,5,  2,6,  3,6
  };

  const int s1[] = {
    // Number of lists
    3,
    // Lists (number of pairs, pair0, pair1, ...)
    5,  1,2,  2,3,  3,4,  4,5,  6,7,
    5,  1,2,  2,3,  3,4,  4,5,  6,7,
    5,  1,2,  2,3,  3,4,  4,5,  6,7
  };

  const int *specs[] = {s0, s1};
  const unsigned n_specs = sizeof(specs)/sizeof(int*);
}

Answer 6

第一次尝试..这是一种比蛮力算法具有改进的平均复杂度降低的算法。 本质上，您在每次迭代中创建长度不断增加的字符串。 这可能不是最好的解决方案，但我们会等待最好的解决方案的出现...:)

从列表 1 开始。该列表中的所有条目都是长度为 2 (#=5) 的有效解决方案
接下来，当您引入列表 2 时，记录长度为 4 的所有有效解，最终为 {1425, 2314, 2315, 2415} (#=4)。

当您将第三个列表添加到混合中时，请重复该过程。 您最终将得到 {142536, 241536} (#=2)。

复杂性的降低已经到位，因为您在每次迭代中都会丢弃坏字符串。 最坏的情况碰巧仍然是相同的——所有对都是不同的。

Answer 7

这感觉像是一个应用约束编程方法的好问题。 对于 Wikipedia 提供的软件包列表，我将补充一点，我过去使用 Gecode 拥有良好的经验; Gecode 示例还提供了约束编程的基本教程。 如果您想深入了解，约束处理是一本关于该主题的好书算法如何工作。