我有一组项目，例如：{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} 表示。
您可能会考虑使用数字池的递归解决方案（在您提供的示例中，它将被初始化为 {1,1,1,2,2,3,3,3}），并在给定的索引处决定作为参数，将哪个数字放置在此索引处（当然，使用您提供的限制）。
如果你愿意，我可以提供伪代码。
你可以建一棵树。级别 0：创建根节点。级别 1：将第一个“限制集”中的每个项目附加为根的子项。级别 2：将第二个限制集中的每个项目附加为每个级别 1 节点的子节点。级别 3：将第三个限制集中的每个项目附加为每个级别 2 节点的子节点。...
排列计数是最终树的叶节点数。
编辑
目前尚不清楚“项目集”{1,1,1,2,2,3,3,3} 是什么意思。如果这是为了限制每个值可以使用多少次（“1”可以使用 3 次，“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 很少的数字。我想说两个决定因素中的最小值应该获胜。
此外，您必须为 Problem 定义一个哈希函数——使用 boost 的哈希值应该不会太难。
可以通过将向量替换为 set<> 并为 unordered_set 定义 < 运算符来改进此解决方案。这会将更多相同的子问题折叠到单个地图元素中，并进一步减少缓解指数爆炸。
可以通过制作相同的问题实例来进一步改进此解决方案，只是将数字重新排列为相同的值并比较为相同。
为了节省空间，您可以构建有向图而不是树。
那么排列的数量就是从根节点到最终集合的节点的路径数。