Generate numerical permutations with conditions and template metaprogramming This, but via template metaprogramming:

template &lt;int n&gt; struct insanity { int[][n] permutations; }


Generate all numbers with n digits (0-9) such that each digit is either:


Zero
The first digit
Already present
Greater than the maximum digit to the left


Don't worry about leading zeros either way.

Valid examples:

012333
012391


Invalid examples:

012945


(Is this even possible?)

Winning code will be explainable and concise, but I'll take a clear short answer over the shortest. 

Clarification on conditions: Shortest code with a complete explanation for what's going on. "Complete" means: Explain it to someone who knows how templates work, but not how TMP works.
Success!!!! It only took me 3 hours or so. (Note: Requires C++11 support)  

4,410 characters (including output functions)

Compiled on GCC 4.7.2 (Ideone)

#include&lt;iostream&gt;
#include&lt;type_traits&gt;

int constexpr powOf10(size_t power)
{
    return power == 0 ? 1 : 10 * powOf10(power - 1);
}

template&lt;int... digits&gt;
struct buildNumber;

template&lt;int first, int... digits&gt;
struct buildNumber&lt;first, digits...&gt; : std::integral_constant&lt;int, first * powOf10(sizeof...(digits)) + buildNumber&lt;digits...&gt;::value&gt;
{
};

template&lt;&gt;
struct buildNumber&lt;&gt; : std::integral_constant&lt;int, 0&gt;
{
};

template&lt;int... digits&gt;
struct areAllDigits;

template&lt;int first, int... digits&gt;
struct areAllDigits&lt;first, digits...&gt;
{
    static bool constexpr value = first &gt; 0 &amp;&amp; first &lt; 10 &amp;&amp; areAllDigits&lt;digits...&gt;::value;
};

template&lt;int first&gt;
struct areAllDigits&lt;first&gt;
{
    static bool constexpr value = first&gt;0 &amp;&amp; first &lt; 10;
};

template&lt;class T&gt;
struct buildNumberT;


template&lt;int... digits&gt;
struct digitContainer
{

};


template&lt;int... digits&gt;
struct buildNumberT&lt;digitContainer&lt;digits...&gt;&gt; : buildNumber&lt;digits...&gt; {};

template&lt;class T1, class T2&gt;
struct concatCtr;

template&lt;int... digits1, int... digits2&gt;
struct concatCtr&lt;digitContainer&lt;digits1...&gt;, digitContainer&lt;digits2...&gt;&gt;
{
    typedef  digitContainer&lt;digits1..., digits2...&gt; type;
};

template&lt;int number, size_t digit&gt;
struct breakIntoDigits
{
    typedef typename concatCtr&lt;digitContainer&lt;number / powOf10(digit)&gt;, typename breakIntoDigits&lt;number % powOf10(digit), digit - 1&gt;::ctr&gt;::type ctr;
};

template&lt;int number&gt;
struct breakIntoDigits&lt;number, 0&gt;
{
    typedef digitContainer&lt;number&gt; ctr;
};

template&lt;int needle, int... haystack&gt;
struct contains;

template&lt;int needle, int first, int... haystack&gt;
struct contains&lt;needle, first, haystack...&gt;
{
    static bool constexpr value = needle == first || contains&lt;needle, haystack...&gt;::value;
};

template&lt;int needle&gt;
struct contains&lt;needle&gt;
{
    static constexpr bool value = false;
};

template&lt;int... values&gt;
struct max;

template&lt;int first, int... rest&gt;
struct max&lt;first, rest...&gt;
{
    static constexpr int value = first &gt; max&lt;rest...&gt;::value ? first : max&lt;rest...&gt;::value;
};

template&lt;&gt;
struct max&lt;&gt;
{
    static int constexpr value = 0;
};

template&lt;class container, int... digits&gt;
struct ruleChecker;

template&lt;int current, int... allPrevious, int... rest&gt;
struct ruleChecker&lt;digitContainer&lt;allPrevious...&gt;, current, rest...&gt;
{
    static bool constexpr value = (current == 0 || sizeof...(allPrevious) == 0 || contains&lt;current, allPrevious...&gt;::value || current &gt; max&lt;allPrevious...&gt;::value) &amp;&amp; ruleChecker&lt;digitContainer&lt;allPrevious..., current&gt;, rest...&gt;::value;
};

template&lt;class container&gt;
struct ruleChecker&lt;container&gt;
{
    static bool constexpr value = true;
};

template&lt;class ctr1, class ctr2&gt;
struct ruleCheckerT;

template&lt;class ctr1, int... set2&gt;
struct ruleCheckerT&lt;ctr1, digitContainer&lt;set2...&gt;&gt; : ruleChecker&lt;ctr1, set2...&gt;{};


template&lt;int number, int length&gt;
struct isValidNumber : ruleCheckerT&lt;digitContainer&lt;&gt;, typename breakIntoDigits&lt;number, length&gt;::ctr&gt;
{
};


template&lt;int number, int length&gt;
struct generateList
{
    typedef typename std::conditional&lt;number % powOf10(length) == 0, 
        digitContainer&lt;&gt;,
        typename concatCtr&lt;
            typename generateList&lt;number + 1, length&gt;::container,
            typename std::conditional&lt;isValidNumber&lt;number, length&gt;::value,
                    digitContainer&lt;number&gt;,
                    digitContainer&lt;&gt;
                &gt;::type
            &gt;::type
        &gt;::type container;
};

template&lt;int number&gt;
struct generateList&lt;number, 1&gt;
{
    typedef typename concatCtr&lt;
        typename generateList&lt;number + 1, 1&gt;::container,
        typename std::conditional&lt;isValidNumber&lt;number, 1&gt;::value,
                digitContainer&lt;number&gt;,
                digitContainer&lt;&gt;
            &gt;::type
        &gt;::type container;
};

#define DEFINE_ENDPOINT_FOR_LENGTH(length) template&lt;&gt; struct generateList&lt;powOf10(length), (length)&gt;{typedef digitContainer&lt;&gt; container;}

template&lt;int length&gt;
struct insanity
{
    static_assert(length &gt; 0, "Length must be greater than 0.");
    typedef typename concatCtr&lt;typename generateList&lt;1, length&gt;::container, digitContainer&lt;0&gt;&gt;::type numberList;
};

template&lt;int first, int... rest&gt;
void outputContainer(digitContainer&lt;first, rest...&gt; values)
{
    std::cout&lt;&lt;first&lt;&lt;'\n';
    outputContainer(digitContainer&lt;rest...&gt;{});
}

void outputContainer(digitContainer&lt;&gt; empty)
{
    std::flush(std::cout);
}


Explanation

insanity is the entry point, as used in the OP.  buildNumber builds a number from a list of digits; breakIntoDigits does the opposite; it takes a number and breaks it into length digits.  areAllDigits is just a helper I used earlier.  It isn't used in the final code.  It's value property is true if all the numbers passed to it are base-10 digits.  It generates a list of valid numbers (validated by isValidNumber) and puts them in a digitContainer (originally I was only going to use this for digits, but I decided to use it for both things).

Limitations


It can only calculate up to the point the compiler errors out from template recursion depth.
You need to define an ending point for each length because otherwise it keeps instantiating templates up to the limit because of std::conditional. You define an ending point for each length by typing DEFINE_ENDPOINT_FOR_LENGTH(i) where i is the length.