# Generate numerical permutations with conditions and template metaprogramming [closed]

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
4. Greater than the maximum digit to the left

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.

• What is the objective winning criteria? Do you have a solution? Jun 15, 2013 at 15:16
• I do not have a solution. Let me clarify my criteria. Jun 15, 2013 at 15:21
• There are a number of things which aren't clear to me. What is a digit (i.e. are you assuming base 10)? What is the purpose of case 4? Why does the title talk about permutations? Jun 15, 2013 at 16:13

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.
• I'm really impressed. I'm slowly getting the time to understand this, but either way, I'll give you the answer in a day or two since you satisfy the criteria. Jun 19, 2013 at 15:43