Generate numerical permutations with conditions and template metaprogramming

Question

This, but via template metaprogramming:

template <int n> struct insanity { int[][n] permutations; }

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

1. Zero
2. The first digit
3. Already present
4. 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.

Answer 1

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<iostream>
#include<type_traits>

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

template<int... digits>
struct buildNumber;

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

template<>
struct buildNumber<> : std::integral_constant<int, 0>
{
};

template<int... digits>
struct areAllDigits;

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

template<int first>
struct areAllDigits<first>
{
    static bool constexpr value = first>0 && first < 10;
};

template<class T>
struct buildNumberT;


template<int... digits>
struct digitContainer
{

};


template<int... digits>
struct buildNumberT<digitContainer<digits...>> : buildNumber<digits...> {};

template<class T1, class T2>
struct concatCtr;

template<int... digits1, int... digits2>
struct concatCtr<digitContainer<digits1...>, digitContainer<digits2...>>
{
    typedef  digitContainer<digits1..., digits2...> type;
};

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

template<int number>
struct breakIntoDigits<number, 0>
{
    typedef digitContainer<number> ctr;
};

template<int needle, int... haystack>
struct contains;

template<int needle, int first, int... haystack>
struct contains<needle, first, haystack...>
{
    static bool constexpr value = needle == first || contains<needle, haystack...>::value;
};

template<int needle>
struct contains<needle>
{
    static constexpr bool value = false;
};

template<int... values>
struct max;

template<int first, int... rest>
struct max<first, rest...>
{
    static constexpr int value = first > max<rest...>::value ? first : max<rest...>::value;
};

template<>
struct max<>
{
    static int constexpr value = 0;
};

template<class container, int... digits>
struct ruleChecker;

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

template<class container>
struct ruleChecker<container>
{
    static bool constexpr value = true;
};

template<class ctr1, class ctr2>
struct ruleCheckerT;

template<class ctr1, int... set2>
struct ruleCheckerT<ctr1, digitContainer<set2...>> : ruleChecker<ctr1, set2...>{};


template<int number, int length>
struct isValidNumber : ruleCheckerT<digitContainer<>, typename breakIntoDigits<number, length>::ctr>
{
};


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

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

#define DEFINE_ENDPOINT_FOR_LENGTH(length) template<> struct generateList<powOf10(length), (length)>{typedef digitContainer<> container;}

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

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

void outputContainer(digitContainer<> 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.