具有额外限制的排列

Question

我有一组项目，例如：{1,1,1,2,2,3,3,3}，以及一组限制集，例如 {{3},{1,2},{1 ,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}。我正在寻找项目的排列，但第一个元素必须是 3，第二个元素必须是 1 或 2，等等。

一个适合的排列是： {3,1,1,1,2,2,3}

有没有一种算法可以统计这个问题的所有排列？此类问题有名称吗？

为了说明，我知道如何针对某些类型的“限制集”解决这个问题。 项目集：{1,1,2,2,3}，限制 {{1,2},{1,2,3},{1,2,3},{1,2},{1,2 }}。这等于 2!/(2-1)!/1! * 4!/2!/2!。首先有效地排列 3 个项目，因为它是最严格的，然后在有空间的情况下排列剩余的项目。

还有...多项式时间。这可能吗？

更新：这将在下面的链接中进一步讨论。上面的问题称为“计算完美匹配”，上面的每个排列限制都由占用者的槽矩阵上的 {0,1} 表示。

• https://math.stackexchange.com/questions/519056/does-a-矩阵表示-双射
• https://math.stackexchange.com /questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots< /a>

Answer 1

为了节省空间，您可以构建有向图而不是树。

• 创建根节点。
• 为每个项目创建一个节点
  第一组，并从根链接到
  新节点。
• 为每个项目创建一个节点
  第二组，以及每个第一组的链接
  将项目设置为每个第二设置项目。
• ...

排列的数量就是从根节点到最终集合的节点的路径数量。

Answer 2

这里的所有其他解决方案都是指数时间的——即使对于不需要的情况也是如此。这个问题表现出类似的子结构，因此应该用动态规划来解决。

你想要做的是编写一个类来记忆子问题的解决方案：

class Counter {
  struct Problem {
     unordered_multiset<int> s;
     vector<unordered_set<int>> v;
  };

  int Count(Problem const& p) {
    if (m.v.size() == 0)
      return 1;
    if (m.find(p) != m.end())
      return m[p];
    // otherwise, attack the problem choosing either choosing an index 'i' (notes below)
    // or a number 'n'.  This code only illustrates choosing an index 'i'.
    Problem smaller_p = p;
    smaller_p.v.erase(v.begin() + i);
    int retval = 0;
    for (auto it = p.s.begin(); it != p.s.end(); ++it) {
      if (smaller_p.s.find(*it) == smaller_p.s.end())
        continue;
      smaller_p.s.erase(*it);
      retval += Count(smaller_p);
      smaller_p.s.insert(*it);      
    }
    m[p] = retval;
    return retval;
  }

  unordered_map<Problem, int> m;
};

代码说明了如何选择索引 i，该索引应该选择在 v[i].size() 较小的地方。另一种选择是选择一个数字 n，它应该是一个可以放置它的位置 v 很少的数字。我想说两个决定因素中的最小值应该获胜。

另外，您必须为问题定义一个散列函数——使用 boost 的散列内容应该不会太难。

可以通过用集合<>替换向量并定义<>来改进该解决方案。 unordered_set 的运算符。这会将更多相同的子问题折叠成单个映射元素，并进一步减少缓解指数爆炸。

通过使问题实例相同，除了将数字重新排列哈希为相同值并比较相同之外，可以进一步改进该解决方案。

Answer 3

您可能会考虑使用数字池的递归解决方案（在您提供的示例中，它将初始化为 {1,1,1,2,2,3,3,3}），并在给定的索引处做出决定作为参数，将哪个数字放置在该索引处（当然，使用您提供的限制）。

如果您愿意，我可以提供伪代码。

Answer 4

你可以建一棵树。
0级：创建根节点。
级别 1：将第一个“限制集”中的每个项目附加为根的子项。
级别 2：将第二个限制集中的每个项目附加为每个级别 1 节点的子节点。
级别 3：将第三个限制集中的每个项目附加为每个级别 2 节点的子节点。
...

排列计数就是最终树的叶节点数。

编辑

目前尚不清楚“项目集”{1,1,1,2,2,3,3,3} 的含义。如果这意味着限制每个值可以使用多少次（“1”可以使用 3 次，“2”可以使用两次，等等），那么我们还需要一个步骤：

• 在将节点附加到树之前，删除这些值用于项目集中的当前路径。如果您想要附加的值仍然可用（例如，您想要附加一个“1”，而“1”到目前为止只使用了两次），则将其附加到树中。