This was my submission for the Dice.com coding contest initially posted at http://news.dice.com/2013/10/02/coding-challenge-046/I came in 7th. Boo.

permute.cpp

//	Code submission for coding challenge "Prove Your Factorial Fluency"
//	http://news.dice.com/2013/10/02/coding-challenge-046/
//
//	Archived at https://web.archive.org/web/20140204075900/http://news.dice.com/2013/10/02/coding-challenge-046/
//
//	Start with the number 987654321 - Assume the count is from that number to the lowest possible permutation
//	value of 123456789, and that all values are sorted from maximum to minimum.  Find the nth value, in this
//	case, the 100,000th value.
//
//	Author:  Richard R. Vasquez, II
//	Website: http://tinymu.gs
//
//	Notes:  This was run in Release - Win32 - Visual Studio 2012
//
//  Personal averages:   ~0.5 seconds : 0.000000043 seconds to find correct solution.
//                       ~1.0 second  : 0.000000034 seconds to find correct solution.
//                       ~5.0 seconds : 0.000000036 seconds to find correct solution.
//                      ~10.0 seconds : 0.000000035 seconds to find correct solution.
//                      ~25.0 seconds : 0.000000034 seconds to find correct solution.
//                      ~50.0 seconds : 0.000000034 seconds to find correct solution.
//
//	I changed algorithm based on a bunch of papers I read over the past couple of weeks.
//
//	I really should have cited my sources, because 10+ years later, I'm drawing a blank.
//	However, there looks to be an even better version located here:
//	https://stemhash.com/efficient-permutations-in-lexicographic-order/
//
//	Then I started banging on the resulting code by unrolling the main loop while
//	throwing the inner loop into a series of switch case dropthroughs.  Then add
//	other tiny optimizations here and there with lookup tables and similar.  It makes
//	for *much* longer code, but it's about 3 orders of magnitude faster, which I'll
//	consider an acceptable tradeoff.

#include <chrono>
#include <iostream>
#include <iomanip>

using namespace std;
void WriteOutput(char* answer, int iterations, double time);

//	How many seconds minimum we want to run
const double seconds = 5.0;
//	Which specific permutation we're looking for (1 based)
const int countTarget = 100000;

//	Lookup tables for fast subtraction.
const int muls8[] = {0, -40320, -80640, -120960, -161280, -201600, -241920, -282240, -322560};
const int muls7[] = {0,  -5040, -10080,  -15120,  -20160,  -25200,  -30240,  -35280};
const int muls6[] = {0,   -720,  -1440,   -2160,   -2880,   -3600,   -4320};
const int muls5[] = {0,   -120,   -240,    -360,    -480,    -600};
const int muls4[] = {0,    -24,    -48,     -72,     -96};
const int muls3[] = {0,     -6,    -12,     -18};
const int muls2[] = {0,     -2,     -4};
const int muls1[] = {0,     -1};

char letters[9] = {'9','8','7','6','5','4','3','2','1'};

int main()
{
	//	Initialization
	std::chrono::steady_clock::time_point Start, End;
	//	Placeholder for the output
	char s[10] = { '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0' };
	//	How many times we've calculated the answer.
	int iterations = 0;

	//	Start ticking time.
	Start = std::chrono::steady_clock::now();
	End = std::chrono::steady_clock::now();
	while(std::chrono::duration_cast<std::chrono::duration<double>>(End-Start).count() < seconds)
	{
		iterations++;
		letters[0] = '9';
		letters[1] = '8';
		letters[2] = '7';
		letters[3] = '6';
		letters[4] = '5';
		letters[5] = '4';
		letters[6] = '3';
		letters[7] = '2';
		letters[8] = '1';
		char c;

		//	We count with 0 based indexes
		int zeroBase = countTarget - 1;

		#pragma region Process 8! permutation value
		int count = zeroBase / 40320;
		c = letters[count];
		switch(count)
		{
			case 8:
				letters[8] = letters[7];
			case 7:
				letters[7] = letters[6];
			case 6:
				letters[6] = letters[5];
			case 5:
				letters[5] = letters[4];
			case 4:
				letters[4] = letters[3];
			case 3:
				letters[3] = letters[2];
			case 2:
				letters[2] = letters[1];
			case 1:
				letters[1] = letters[0];
				letters[0] = c;
				break;
			default:
				break;
		}
		zeroBase += muls8[count];
		#pragma endregion

		#pragma region Process 7! permutation value
		count = zeroBase / 5040;
		c = letters[count + 1];
		switch(count)
		{
			case 7:
				letters[8] = letters[7];
			case 6:
				letters[7] = letters[6];
			case 5:
				letters[6] = letters[5];
			case 4:
				letters[5] = letters[4];
			case 3:
				letters[4] = letters[3];
			case 2:
				letters[3] = letters[2];
			case 1:
				letters[2] = letters[1];
				letters[1] = c;
				break;
			default:
				break;
		}
		zeroBase += muls7[count];
		#pragma endregion

		#pragma region Process 6! permutation value
		count = zeroBase / 720;
		c = letters[count + 2];
		switch(count)
		{
			case 6:
				letters[8] = letters[7];
			case 5:
				letters[7] = letters[6];
			case 4:
				letters[6] = letters[5];
			case 3:
				letters[5] = letters[4];
			case 2:
				letters[4] = letters[3];
			case 1:
				letters[3] = letters[2];
				letters[2] = c;
				break;
			default:
				break;
		}
		zeroBase += muls6[count];
		#pragma endregion

		#pragma region Process 5! permutation value
		count = zeroBase / 120;
		c = letters[count + 3];
		switch(count)
		{
			case 5:
				letters[8] = letters[7];
			case 4:
				letters[7] = letters[6];
			case 3:
				letters[6] = letters[5];
			case 2:
				letters[5] = letters[4];
			case 1:
				letters[4] = letters[3];
				letters[3] = c;
				break;
			default:
				break;
		}
		zeroBase += muls5[count];
		#pragma endregion

		#pragma region Process 4! permutation value
		count = zeroBase / 24;
		c = letters[count + 4];
		switch(count)
		{
			case 4:
				letters[8] = letters[7];
			case 3:
				letters[7] = letters[6];
			case 2:
				letters[6] = letters[5];
			case 1:
				letters[5] = letters[4];
				letters[4] = c;
				break;
			default:
				break;
		}
		zeroBase += muls4[count];
		#pragma endregion

		#pragma region Process 3! permutation value
		count = zeroBase / 6;
		c = letters[count + 5];
		switch(count)
		{
			case 3:
				letters[8] = letters[7];
			case 2:
				letters[7] = letters[6];
			case 1:
				letters[6] = letters[5];
				letters[5] = c;
				break;
			default:
				break;
		}
		zeroBase += muls3[count];
		#pragma endregion

		#pragma region Process 2! permutation value
		count = zeroBase / 2;
		c = letters[count + 6];
		switch(count)
		{
			case 2:
				letters[8] = letters[7];
			case 1:
				letters[7] = letters[6];
				letters[6] = c;
				break;
			default:
				break;
		}
		zeroBase += muls2[count];
		#pragma endregion

		#pragma region Process 1! permutation value
		count = zeroBase;
		switch(count)
		{
			case 1:
				swap(letters[7], letters[8]);
				break;
			default:
				break;
		}
		#pragma endregion
		End = std::chrono::steady_clock::now();
	}

	for(int i = 0; i < 9; i++)
	{
		s[ i ] = letters[ i ];
	}

	WriteOutput( s, iterations, 
		std::chrono::duration_cast<std::chrono::duration<double>>(End-Start).count()
		);

	//std::cin.get();	//uncomment to pause before ending.
	return 0;
}

//	Quick output of the answer, and the average time spent
//	based on total time / number of iterations.  Expanded out
//	to nanoseconds since the speed of this algorithm on my
//	machine initially only showed 1 microsecond.
void WriteOutput(char* answer, int iterations, double time)
{
	double timePerIteration = time / (double) iterations;
	int seconds = (int) timePerIteration;
	int minutes = seconds / 60;
	double partial = timePerIteration - seconds;
	
	cout
		<< answer << endl << endl << minutes
		<< " minutes, " << fixed << setprecision( 9 )
		<< partial << " seconds (" << iterations
		<< " iterations in "  <<  time
		<< " seconds)" << endl;
}