CODEWITHSUNDEEP
c++permutationrestriction
ATYslh
ATYslh

Reputation: 80

Efficient way to compute unique permutations with restrictions

so I know that there are a lot of ways to compute unique permutations. Usually it is slower to apply restrictions during the generation than removing them afterwards. So let's say I have a vector of 10 elements. For the sake of an example:

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

I have the unique restriction that I know that I am not allowed to have the same three numbers in a row, so all permutations containing {8,8,8} in any place would be invalid. In case I have a giant array of e.g. 20 elements I would assume that I could save a lot of time if I skip all permutations that start with {8,8,8}.

Is there any to do anything like this efficiently? How do I figure out at which point it makes sense to add the additional slowdown of checking each permutation?

Upvotes: 3

Views: 191

Answers (1)

Jarod42
Jarod42

Reputation: 217810

With your restriction, while iterating in order, it is possible to skip the block of invalid permutations, from the first invalid one.

The first invalid permutation from number of the form

y y y 8 8 x x 8 x

is

y y y 8 8 8 x1 x2 x3 with x1 < x2 < x3.

so you can go directly to last invalid permutation with

y y y 8 8 8 x3 x2 x1 with x1 < x2 < x3.

so just reverse the last numbers.

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

Upvotes: 3

Related Questions