c++ - 计算具有限制的唯一排列的有效方法

Question

所以我知道有很多方法可以计算唯一排列。通常在生成期间应用限制比在生成之后删除它们要慢。假设我有一个包含 10 个元素的 vector 。举个例子:

std::vector<int> v = {7, 5, 16, 8, 5, 8, 1, 7, 3, 25, 109, 8};

我有一个独特的限制，我知道我不允许连续出现三个相同的数字，因此在任何地方包含 {8,8,8} 的所有排列都是无效的。万一我有一大堆例如20 个元素 如果我跳过所有以 {8,8,8} 开头的排列，我认为我可以节省很多时间。

有没有什么可以有效地做这样的事情？我如何确定在什么时候增加检查每个排列的额外减速是有意义的？

Answer 1

根据您的限制，在按顺序迭代时，可以从第一个无效排列开始跳过无效排列 block 。

表格数字的第一个无效排列

y y 8 8 x x 8 x

是

y y y 8 8 8 x1 x2 x3 且 x1 < x2 < x3。

所以你可以直接转到最后一个无效排列

y y y 8 8 8 x3 x2 x1 且 x1 < x2 < x3。

所以只需反转最后的数字即可。

bool is_valid(const std::vector<int>& v)
{
    auto it = std::find(v.begin(), v.end(), 8);
    
    return v.end() - it >= 3 && (*it != *(it + 1) || *it != *(it + 2));
}

void go_to_last_invalid(std::vector<int>& v)
{
    auto it = std::find(v.begin(), v.end(), 8);
    std::reverse(it + 3, v.end());
}

int main()
{
    std::vector<int> v = {1, 7, 7, 8, 8, 8, 9, 10};
    do {
        if (!is_valid(v)) { go_to_last_invalid(v); continue; }
        for (auto e : v) { std::cout << e << " "; } std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
}

Demo