#include <algorithm>
#include <array>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>

#define PRECOMPUTE_RANDOM 1

bool isPermutation(const std::string &inputa, const std::string &inputb)
{
  static const size_t MAX_CHAR = 256;
  std::array<int, MAX_CHAR> allChars;
  allChars.fill(0);

  for (auto c : inputa)
    ++allChars[c];

  for (auto c : inputb)
  {
    --allChars[c];
    if (allChars[c] < 0)
      return false;
  }

  return true;
}

bool isPermutationSort(const std::string& a, const std::string& b) {
	return std::is_permutation(a.begin(), a.end(), b.begin());
}

int main()
{
  const std::vector<std::string> bag
  {
    "god", "dog", "thisisaratherlongerinput", "thisisarathershorterinput",
    "armen", "ramen"
  };

  const unsigned stop = 1000000;

#if !PRECOMPUTE_RANDOM
  static std::mt19937 engine;
  std::uniform_int_distribution<std::size_t> rand(0, bag.size() - 1);
#else
  static size_t engine = 0;
  static unsigned int evals[4 * stop];
{
  static std::mt19937 engine;
  std::uniform_int_distribution<std::size_t> rand(0, bag.size() - 1);
  for(unsigned int i = 0; i < sizeof(evals)/sizeof(*evals); ++i)
    evals[i] = rand(engine);
}
  auto rand = [](size_t& engine) {
    return evals[engine++];
  };
#endif

  unsigned counter = 0;
  std::clock_t start = std::clock();
  for (unsigned i(0); i < stop; ++i)
    counter += isPermutation(bag[rand(engine)], bag[rand(engine)]);

  double time = (clock() - start) / (double)CLOCKS_PER_SEC;
  std::cout << counter << ": " << time << " s\n";

  counter = 0;
  start = std::clock();
  for (unsigned i(0); i < stop; ++i)
    counter += isPermutationSort(bag[rand(engine)], bag[rand(engine)]);

  time = (clock() - start) / (double)CLOCKS_PER_SEC;
  std::cout << counter << ": " << time << " s\n";

  return 0;
}