The problem is stated in the following way: compute the number of Roman numerals where no letter appears twice. For example XCIV and XVI are OK, XXI is not.
The range includes I through MDCLXVI which includes every Roman ‘digit’ once. Obviously by picking any number of those ‘digits’ in this order we get a Roman numeral fulfilling the conditions. There can be 2^7 – 1 such numerals, excluding the trivial case where none was picked. However 127 is only the lower bound since this formula does not cover subtractions like CM, XL, IV.
To continue we need to establish the rules for the subtractions. According to Wikipedia the only allowed cases when a smaller ‘digit’ can precede a larger one are:
- C before M, D
- X before C, L
- I before X, V
Therefore IV, IX, XLI, CMXLIV are all fine. VL, XD are not. Also subtractions from the letter/’digit’ 10 times larger preclude the use of the jumped ‘digit’. XCL, IXV are incorrect.
To generate all the numerals without repetitions we will start with M. There are two choices: either we use M in your numeral, or not. Go down recursively via D. It starts getting interesting after reaching C. Now there are not two, but four choices:
- Skip it,
- use it in a direct way,
- use it as a prefix to the previous ‘digit’ (D) if we chose it previously
- use it as a prefix to the ‘digit’ two steps back (M) if we chose it previously
With X there is another condition: it can only precede C if C is itself used in the direct way. Same for I which can form IX but not IXC.
The algorithm enumerating all Roman numbers is now completely formed. We will use a 7 element array to store the way the letters MDCLXVI are used. The possible values are:
- not used
- subtracting from the digit one step back
- subtracting from the digit two steps back
- used directly for the face value
The two ‘subtracting’ cases need only be differentiated if we want to actually print the Roman numerals. As the task is to compute the number of numerals without repetitions we will only keep the distinction between a letter used ‘positively’ and ‘negatively’.
We’ll call our function find() with the parameters position=0 and array of chosen letters = 0, 0, 0, 0, 0, 0, 0 referring to M, D, C, L, X, V, I. The pseudocode is as follows:
find(position, chosen)
if position == 7 then no more choices, return 1;
mark chosen[position] as used directly; call find(position + 1, chosen) and store the result as the count
mark chosen[position] as unused; call find(position + 1, chosen) and add the result to the count
if position refers to C, X, I (preceding letters) then {
if the letter two steps back was used directly and the previous letter was not used then mark chosen[position] as used indirectly; call find(position + 1, chosen) and add the result to the count
if the letter one step back was used directly then mark chosen[position] as used indirectly; call find(position + 1, chosen) and add the result to the count
}
return count
The C version somewhat obfuscated and with certain optimizations (no need to call find twice for the indirect case) can be found here:
http://codepad.org/D1Sesi4Q
or here:
#include <stdio.h>
#define RN 7
#define BK 1
#define USE 2
#define recurse(x) { s[p]=(x); count += times * find(p + 1, s); }
typedef unsigned int uint;
uint find(uint p, uint* s)
{
uint count = 0;
if (p == RN) return 1;
uint times = 1;
recurse(USE);
recurse(0);
if (p > 0 && p % 2 == 0)
{
times = (uint)(s[p - 2] == USE && !s[p - 1]) + (uint)(s[p - 1] == USE);
if (times) recurse(BK);
}
return count;
}
int main(int argc, char** argv)
{
uint s[RN] = {0, 0, 0, 0, 0, 0, 0};
uint count = find(0, s);
printf("%d\n", count - 1);
return 0;
}
From C/C++ to Python 