具有额外限制的排列

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-matrix-represent-a-bijection
• 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

Answer 1

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

您想要做的是编写一个存储子问题解决方案的类：

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 的散列内容应该不会太难。

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

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