Your problem is that, despite the fact that your data is ordered, this order is arbitrary. The "distance" between "muslim" (enum val=1) to "hindu" (enum val=3) is not 2.
The most straight-forward way of tackling this issue is to convert enum values to binary indicator vectors:
Suppose you have
enum {
Catholic = 0
Protestant,
Muslim,
Jewish,
Hindu,
...
NumOfRel };
You replace the single entry of enum val with a binary vector of length NumOfRel
with zeros everywhere except for a single 1
at the appropriate place:
For a Protestant entry, you'll have the following binary vector:
[ 0 1 0 0 ... ]
For a Jewish:
[ 0 0 0 1 0 ... ]
And so on...
This way, the "distance" between different religions is always 1.