LoL Worlds 2020 Groups Probabilities

#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
#include <algorithm>
#include <stdexcept>
#include <cmath>

enum class Region
{
    CN,
    EU,
    KR,
    NA,
    PCS
};

struct Team
{
    Region region;
    std::string name;
};

constexpr int N_POOLS = 4;
constexpr int N_GROUPS = 4;

bool drawGroupsRec(const std::vector<std::vector<Team>>& teams,
                    const std::vector<std::vector<int>>& drawOrder,
                    std::vector<std::vector<int>>& teamsInGroups,
                    int currentPool,
                    int currentDrawInPool)
{
    if (currentDrawInPool == N_GROUPS)
    {
        if (++currentPool == N_POOLS)
            return true;
        currentDrawInPool = 0;
    }

    auto& teamDrawn = teams[currentPool][drawOrder[currentPool][currentDrawInPool]];

    for (size_t i = 0; i < N_GROUPS; i++)
    {
        if (teamsInGroups[i][currentPool] >= 0)
            continue;

        bool sameRegionInGroup = false;

        for (size_t j = 0; j < currentPool; j++)
        {
            auto& teamChecked = teams[j][teamsInGroups[i][j]];
            if (teamDrawn.region == teamChecked.region)
            {
                sameRegionInGroup = true;
                break;
            }
        }

        if (sameRegionInGroup)
            continue;

        // Try to draw the rest with this placement. Rewind if it fails
        teamsInGroups[i][currentPool] = drawOrder[currentPool][currentDrawInPool];

        if (drawGroupsRec(teams, drawOrder, teamsInGroups, currentPool, currentDrawInPool + 1))
            return true;

        teamsInGroups[i][currentPool] = -1;
    }

    return false;
}

std::vector<std::vector<int>> drawGroups(const std::vector<std::vector<Team>>& teams,
                                         const std::vector<std::vector<int>>& drawOrder)
{
    std::vector<std::vector<int>> teamsInGroups(N_GROUPS, std::vector<int>(N_POOLS, -1));

    if (!drawGroupsRec(teams, drawOrder, teamsInGroups, 0, 0))
    {
        throw std::logic_error{"No valid group possible"};
    }

    return teamsInGroups;
}

namespace std
{
    template<typename T>
    struct hash<vector<T>>
    {
        size_t operator()(vector<T> const& vec) const
        {
            size_t seed = vec.size();
            for(auto& i : vec) {
                seed ^= hash<T>{}(i) + 0xc4ceb9fe1a85ec53 + (seed << 6) + (seed >> 2);
            }
            return seed;
        }
    };
}

constexpr int factorial(int n)
{
    int ret = 1;
    for(int i = 1; i <= n; ++i)
        ret *= i;
    return ret;
}

int main()
{
    const std::vector<std::vector<Team>> teamsInPools {
        {{Region::CN, "TES"}, {Region::EU, "G2"}, {Region::KR, "DAMWON"}, {Region::NA, "TSM"}},
        {{Region::CN, "JDG"}, {Region::EU, "FNC"}, {Region::KR, "DRX"}, {Region::CN, "SNG"}},
        {{Region::PCS, "MACHI"}, {Region::EU, "RGE"}, {Region::KR, "GENG"}, {Region::NA, "FLY"}},
        {{Region::CN, "LGD"}, {Region::EU, "MAD"}, {Region::PCS, "PSG"}, {Region::NA, "TL"}}
    };

    std::vector<std::vector<int>> drawOrder (N_POOLS, {0, 1, 2, 3});
    std::unordered_map<std::vector<int>, int> groupOccurrences;
    std::unordered_map<std::vector<std::vector<int>>, int> groupCombinationOccurrences;

    do
    {
        do
        {
            do
            {
                do
                {
                    auto teamsInGroups = drawGroups(teamsInPools, drawOrder);
                    std::vector<std::vector<int>> orderedGroups(N_GROUPS);
                    for (size_t i = 0; i < N_GROUPS; i++)
                    {
                        orderedGroups[teamsInGroups[i][0]] = teamsInGroups[i];
                        ++groupOccurrences[teamsInGroups[i]];
                    }
                    ++groupCombinationOccurrences[orderedGroups];
                } while (std::next_permutation(drawOrder[3].begin(), drawOrder[3].end()));
            } while (std::next_permutation(drawOrder[2].begin(), drawOrder[2].end()));
        } while (std::next_permutation(drawOrder[1].begin(), drawOrder[1].end()));
    } while (std::next_permutation(drawOrder[0].begin(), drawOrder[0].end()));

    const double nPermutations = std::pow(factorial(N_GROUPS), N_POOLS);

    std::cout.precision(2);
    std::cout << std::fixed;

    for (const auto& [groupCombination, occurrence] : groupCombinationOccurrences)
    {
        std::cout << "Group combination occurs " << 100 * occurrence / nPermutations << "% of the time\n";
        for (const auto& group : groupCombination)
        {
            for (int i = 0; i < group.size(); ++i)
            {
                std::cout << teamsInPools[i][group[i]].name << ' ';
            }
            std::cout << '\n';
        }
    }

    std::cout << '\n';
    for (const auto& [group, occurrence] : groupOccurrences)
    {
        std::cout << "Group occurs " << 100 * occurrence / nPermutations << "% of the time\n";
        for (int i = 0; i < group.size(); ++i)
        {
            std::cout << teamsInPools[i][group[i]].name << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}