Intel's Ronler Acres Plant

Silicon Forest

Sunday, May 17, 2015

Permutations


John Whitney - Permutations (1966)
There is only a tenuous link between this video and this post.

coding game dot com has a number of programming puzzles. One program I attempted required generating permutations of a small number of digits. This is a common enough requirement that I figured someone had already sorted it, and a quick Google search delivered up an example.
    The example was just what I needed, but being a bit thick at the time I failed to grok just why it worked, so I set out to write my own version based on how I would generate permutations of, say, four digits. I made a couple of attempts, but no success. I put it aside.
    I've been playing a game called 0h h1. It's a relatively simple logic game that involves filling a small checkerboard with red and blue squares according to some rules. After I had been playing it for a while, I started noticing that a line containing some combinations of just a few squares had only one possible solution, while others with more spots taken still had a number of possible solutions.
    This leads to my writing a program to calculate the number of possible arrangements for a single line. It took me a day or so to figure out how to do it. It was mostly a matter of the way I framed the question. I was thinking there should be a magic formula for calculating the number of possible combinations you could use to fill out a line, and there might be but I haven't figured out just what it would be. Yet. My program counts the possible solutions and I am reasonably confident that the number is correct.

Length    Permutations
   4           6
   6          14
   8          34
  10          84
  12         208

The constraints are that you cannot have more than two of the same symbols in a row and each row contains an equal number of each symbol.

    Coding this program opened my eyes to a way to solve the original permutation problem, which I did and it worked. I was kind of hoping that my method would be faster than the standard method, but no such luck.
    I now have three different programs that all do variations of the same thing. Half of each program has the same basic elements, so I combined them into one program and added a switch to select which version to run. I uploaded it to Github. You can find it here.
    The possible number of permutations of a number (N) of unique digits (or any other symbols) is N factorial, or N! in math speak. Factorials grow very fast. 12! is the biggest factorial you can fit in a 32-bit integer. (A 32-bit integer on a computer can contain a value of four billion and change.)  64-bit integers are now pretty standard. They will hold 20!. My program should handle up to 20 digits, though no one will ever know as it would take a zillion years to generate all the possible values.
    Anyway, now that I've got the permutation thing sorted out I can go back to working on the original problem.

P.S. A bit from the Wikipedia article about John Whitney:
The analogue computer Whitney used to create his most famous animations was built in the late 1950s by converting the mechanism of a World War II M-5 antiaircraft gun director.
I'm thinking WW2 anti-aircraft guns and the 'computers' used to aim them were the very peak of mechanical technology. The machinery was 16 kinds of complicated, the range was the very limit of what can be done with a gun, the whole operation had to be performed in seconds and there were hundreds, if not thousands of operating guns. There may have been some cold war stuff that was more complicated, but much of it was done with electronics, and none of it was ever used as much as AA guns were used during WW2.

2 comments:

Ole Phat Stu said...

Factorials are useful elsewhere too :-

A number P is prime if and only if ((P-1)!+1)mod(P)=0 :-)

Charles Pergiel said...

Your formula works, though I'm not sure how 'useful' it is. Google docs can only handle values up to 13. It is an interesting phenomena though. I might have to pull out an extended math library and see how far it will go before we run out of time. Or space. I've added your formula to the same Google spreadsheet.