Math Puzzle: Enumerating Combinatorial Result Sets

Warning: Big-time nerder alert! If you find overt nerdyness offensive, zone out now or just click right on through.

I’m neither a computer scientist not a mathematician (and it probably shows), but I’m curious enough to poke around a bit. Lately I’ve been having fun with combinatorics.

One of the programs I often write as I’m learning a new programming language is a cryptogram maker. A cryptogram is basically it a word puzzle where each letter of a piece of text has been replaced by another letter according to a randomized substitution cipher. Here’s an example:

BEFORE: The quick brown fox jumped over the lazy dogs.
AFTER : QGF JKHDY ZESRP WSV CKUIFN SOFE QGF BMXL NSTA.
LETTER : ABCDEFGHIJKLMNOPQRSTUVWXYZ
CYPHER : MZDNFWTGHCYBUPSIJEAQKORVLX

Anyway, I’ve long known the total number of possible cypher keys (supposing that any letter can be replaced with itself), but I’ve spent several boring church meetings thinking about another simple combinatorics problem. Of course, it’s probably pretty basic to one who has studied combinatorics, but I’ll put it to you just the same.

The question was:

How do I process any given cypher key so that an ordered ’solution number’ can be derived from it (or vice versa) without iterating through the possible cyphers (or solutions).

After having the answer suddenly dawn on me the other night, I now put you to the test. And to make it only slightly more interesting, the first person to comment with the answers and an accurately described algorithm (complete with the basic math behind it) wins a whopping $5 cash prize mailable by me. Note that just writing a script to cycle through does not count because the whole point is not to iterate through all the cyphers. Also, I shrunk the alphabet to make it nicer on you. :)

Solution Number Cypher
1 ABCDEFGHIJ
2 ABCDEFGHJI
3 ABCDEFGIHJ
4 ABCDEFGIJH
5 ABCDEFGJHI
6 ABCDEFGJIH
7 ABCDEFHGIJ
… …
? HDICAGEJFB
… …
3096542 ?
… …
? JIHGFEDCBA

Show your logic!  (Hint you can easily do the math on half a sheet of paper once you know the algorithm.)

Aside: This is not a particularly problematic problem (since I really had no need for a solution), but the math is fun just the same. I tried to think of a story problem that would make the math more compelling and less numerically intensive (without truncating the alphabet), but I sort of got bored of writing it. Maybe I’ll share what I came up with later.

If you liked this post, you may want to subscribe to my RSS feed. Thanks for visiting!

categories Nerdiness, Technology | datetime June 25, 2008 1:09 am

4 Comments

  • By Eric, June 25, 2008 @ 12:37 pm

    Interesting little challenge.

    Answers: 2692884, IEHCGDFAJB, 3628800

    Algorithm, in Python:
    from operator import mul
    alphabet = "ABCDEFGHIJ"

    def perms(n):
        return reduce(mul, range(1, n + 1), 1)

    def cypher(number):
        number -= 1
        letters = list(alphabet)
        result = []
        value = perms(len(letters))
        while letters:
            value //= len(letters)
            index = number // value
            result.append(letters.pop(index))
            number -= value * index
        return str.join("", result)

    def number(cypher):
        letters = list(alphabet)
        value = perms(len(letters))
        result = 1
        for letter in cypher:
            value //= len(letters)
            index = letters.index(letter)
            letters.pop(index)
            result += index * value
        return result

    for num in range(1,8):
        cy = cypher(num)
        result = number(cy)
        print (num, cy, result)

    cy = "HDICAGEJFB"
    print (number(cy), cy)

    num = 3096542
    print (num, cypher(num))

    cy = "JIHGFEDCBA"
    print (number(cy), cy)

  • By Jordan, June 26, 2008 @ 12:03 am

    Eric,

    The code is beautiful and the answers are correct. I’ll try to post a little more of the math behind it for the non-programmers out there, but until then, where do I send the prize money? (You can email me off the record.)

    Also, did you know this math from school, or did you just figure it out?

    Lastly, I was interested that for the last question you invoked your number function again. I had expected something like perms(len(alphabet)) since ‘JIHGFEDCBA’ was the last possible solution in the set (and frankly the easiest question on there). Your usage was an excellent sanity check to further verify that your number function worked properly.

  • By Eric, June 26, 2008 @ 8:52 am

    The permutation formula I learned in high school; the actual algorithms I wrote on the fly. The problem has some similarities with various projects I have worked on over the years; I expect that this code could end up in something, though I hadn’t thought of the problem on my own. (I vaguely recall using a permutation generator somewhere, but I’m not finding it at the moment.)

    What the posted code doesn’t show is that I had a few more sanity checks in the last three cases, checking that num == number(cypher(num)) and cy == cypher(number(cy)). I accidentally left those sanity checks in the first part because it wasn’t as obvious with the single-digit numbers. To be honest, though, I partly used number() instead of perms() because I trusted the results of the former more than the correctness of the latter.

    To be honest, the hardest part was getting the code to look good in the message preview.

  • By Reed, July 10, 2008 @ 10:44 am

    Jordan,
    Here is a fun problem I ran into at work. A manufacturing process for a certain part consists of various steps. Let’s say 5 steps to make it simple. Each step has a certain risk associated with it for causing defects in the part (which require tons of paperwork and actual rework to make the part acceptable). Combining all of these risks together give you the overall risk that something will be wrong with the part–this is bad. The fun questions to be answered are:
    1. How AND TO WHAT DEGREE does varying the number of possible defect types influence your overall defect rate?
    2. How AND TO WHAT DEGREE does the value of each individual defect rate affect the overall defect rate?
    3. How does each (1. and 2.) combine
    3. What is the formula that yields the overall defect rate? It’s probably pretty easy (college-level probablity class). This is my challenge to you.

    I just did a simulation using excel for my work problem, and it was fun. Jordan, WILL YOU take this challenge? If you or any of your readers can do it without outside help, I will give buy you french fries when I return. (That’s right, you get the fries, no matter who solves it).

Leave a comment