#include <algorithm>
#include <iostream>
#include <string>
#include <iomanip>

class Hasher
{
public:
    int count = 0;

    int hash(int a, int b)
    {
        count += 1;
        return a ^ b; // Pretend this is a very cryptographically secure one way hash function
    }
};

// Calculates number of "rehashes" we need to make for this iteration
int calculate_number_of_rehashes(int iteration, int n)
{
    if (iteration == 0)
    {
        // First iteration. Calculate hash for entire list
        return n;
    }

    int i = 2;
    while (iteration % i == 0)
    {
        iteration /= i;
        i += 1;
    }
    return i;
}

int main()
{
    size_t n = 10;
    std::vector<int> input(n);
    std::vector<int> hashes(n);
    std::vector<int> counts(n);
    int iteration = 0;
    Hasher hasher;

    for (int i = 0; i < n; i++)
    {
        input[i] = i;
        counts[i] = 0;
    }

    do
    {
        int number_of_rehashes = calculate_number_of_rehashes(iteration, n);
        for (int i = n - number_of_rehashes; i < n; i++)
        {
            counts[i] += 1;
            if (i == 0)
            {
                hashes[i] = hasher.hash(42, input[i]);
            }
            else
            {
                hashes[i] = hasher.hash(input[i - 1], input[i]);
            }
        }
        iteration += 1;
    }
    while (std::next_permutation(input.begin(), input.end()));

    std::cout << "Hashes: " << hasher.count << std::endl;
    std::cout << "Iterations: " << iteration << std::endl;

    // Note how this number converges closer and closer to e = 2.718281828
    std::cout << "Factor: " << std::setprecision(15) << (double) hasher.count / iteration << std::endl;

    std::cout << "Counts: " << std::endl;
    for (int i = 0; i < n; i++)
    {
        std::cout << i << ": " << counts[i] << std::endl;
    }
}

/*
Results:

n = 10:
    Hashes: 9864100
    Iterations: 3628800
    Factor: 2.71828152557319
    Counts:
    0: 10
    1: 90
    2: 720
    3: 5040
    4: 30240
    5: 151200
    6: 604800
    7: 1814400
    8: 3628800
    9: 3628800

    real    0m0.362s
    user    0m0.362s
    sys     0m0.000s

n = 11:
    Hashes: 108505111
    Iterations: 39916800
    Factor: 2.71828180114638
    Counts:
    0: 11
    1: 110
    2: 990
    3: 7920
    4: 55440
    5: 332640
    6: 1663200
    7: 6652800
    8: 19958400
    9: 39916800
    10: 39916800

    real    0m4.044s
    user    0m4.044s
    sys     0m0.000s

n = 12:
    Hashes: 1302061344
    Iterations: 479001600
    Factor: 2.71828182619849
    Counts:
    0: 12
    1: 132
    2: 1320
    3: 11880
    4: 95040
    5: 665280
    6: 3991680
    7: 19958400
    8: 79833600
    9: 239500800
    10: 479001600
    11: 479001600

    real    0m47.669s
    user    0m47.669s
    sys     0m0.000s

*/