Problem #24 easy

Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Additional Notes

This problem requires finding the millionth permutation in lexicographic order of the digits 0-9. The solution uses std::next_permutation from the C++ standard library, which generates the next permutation in order efficiently.

The code includes both a “cheat” mode that brute-forces to the millionth permutation and stubs for a more mathematical approach using factorials.

cpp

Implementations

The "cheat" mode uses std::next_permutation to generate permutations until reaching the millionth, which is efficient for small inputs like 10 digits (O(1) effectively since 10! is manageable).

View Raw

#include <algorithm>
#include <chrono>
#include <iostream>
#include <string>

std::string lexicographic_permutations_cheat(std::string input)
{
  // std::sort(input.begin(), input.end());
  int perm_count = 0;
  std::string result;
  do {
    result = input;
    // std::cout << result << std::endl;
  } while(std::next_permutation(input.begin(), input.end()) && ++perm_count < 1000000);

  return result;
}

uint64_t factorial(uint64_t num)
{
  uint64_t result = 1;
  for(uint64_t i = 1; i <= num; i++) {
    result *= i;
  }
  return result;
}

std::string lexicographic_permutations(std::string input)
{
  std::cout << "Input: " << input << std::endl;
  return input;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
  std::string solution = "2783915460";
  std::string digits("0123456789");
  std::cout << "Solution: " << solution << std::endl;

  std::chrono::high_resolution_clock hr_clock;
  // ------8<----Cheat mode-------8<-------
  std::cout << "Cheat mode" << std::endl;
  auto start_time = hr_clock.now();
  std::string my_answer = lexicographic_permutations_cheat(digits);
  auto end_time = hr_clock.now();
  std::cout << "Answer: " << my_answer << std::endl;
  auto duration = end_time-start_time;
  std::cout << "Time: " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << std::endl;
  std::cout << "Correct?: " << (my_answer == solution ? "PASS" : "FAIL") << std::endl;
  // ------8<----Cheat mode-------8<-------

  // ------8<----Non Cheat Mode---8<-------
  std::cout << "Factorial test: " << factorial(5) << std::endl;
  // ------8<----Non Cheat Mode---8<-------

  // std::cout << "Answer: " << lexicographic_permutations(digits) << std::endl;
}
#endif //#if ! defined UNITTEST_MODE

All Solutions