Computer Counting Algorithms

Often it's necessary to setup a computer program to try all combinations of certain characters.  For example. you might be doing brute-force password recovery and know that the password is 7 digits long and consists only of numbers.  Therefore, you'd want to try every combination of 0-9 that is 7 digits long:

This is nothing more than simple counting and can easily be represented with code similar to the following:

But, suppose that you are able to narrow things down.  Suppose you know how many digits long it is and you know exactly what characters are used, but you just don't know the exact sequence of these characters.  Or, suppose you want to try arranging N objects into all of the possible ways of arranging them:

Mathematically, this yields N-Factorial combinations.  In the above example of 3 objects, that is 3! = 1 x 2 x 3 and such counting is fairly easy to do by hand on paper, but how do you effectiently make a computer count in this fashion?

One way is to use the previous M ^ N counting where M = N and add an additional check that compares each digit with the others and if all aren't unique to ignore that sequence:

But, as you can see this is extremely inefficient.  Out of 3 ^ 3 = 27 sequences, only 6 are used.  And this gets worse as the numbers get larger.  For our 7 character case, that means we are counting 7 ^ 7 = 823543 combinations to use only 7! = 5040 of them.  And that isn't even counting all of the extra comparisons the computer has to do to make sure each digit is unique!

There has to be a more efficient method, right?  Yes there is.  There are probably numerous ways of doing this, but here's one that I figured out one afternoon:

The way we've counted in our above example of 3 objects with 1 2 3 then 1 3 2 then 2 1 3, etc, is very difficult to represent programatically.  But what if we modified it slightly:

Here we increment the first position and then look through the sequence and find the position that holds the number we just incremented the first digit to and we give that position the old number from the first position:

Since each position has a unique value, we know that no other position held the same value from before our incrementation.  And we know that one and only one position conflicts with the new value.  So we simply play a swapping game.  And, we keep this up until the entire sequence is reversed -- that is, when 1 2 3 becomes 3 2 1.

Is that it?  Is that all there is to it?  Well, no not quite.  That's all that is required for 3 or less objects, but it will become apparent as we increase the number of objects that we are missing something.  Let's look at 4 objects and go through the entire counting sequence as we just described:

Oh No!  After only half of the sequence, the counting ended up right back where it started.  We should have gotten 4! = 24 unique sequences, but we only got 12.  So what went wrong??

Well, it turns out that everything is mirrored around the center.  For 2 objects, the first column is paired with the 2nd column.  For 3 objects, the first column is paired with the 3rd column and the 2nd with itself.  But when we reach 4 objects, the 1st column is paired with the 4th column and the 2nd is paired with the 3rd, and everything is mirrored around an invisible line down the center.

When we reach 5 objects, the first column will again be paired with the last column.  The second column will be paired with the next to last column and the center column will pair with itself.  Thus, 4 object and 5 object counting work the same, just like 2 object and 3 object counting works the same:

To explain how to fix our counting algorithm, let's assign a position or index number to each column.  For mathematical convenience, we'll start with 0 and call the first column "column number 0".  The next column will be "column number 1" and so forth, making the last column "column number N-1".

It turns out that whenever you increment a position and that position "rolls over" and then you do the value swap with the mirrored or paired column for the position, then you'll be reverting back to previously visited sequence.  In this example of 4 objects, when we reached 4 2 3 1 and our counting rolled from 4 back to 1 and then we swapped the 1 to a 4 on our paired column (in this case the last column), then we returned back to 1 2 3 4, a previously visited number.

If we carefully examine what is happening, we'll find that each position counts from (index+1) to (N-index).  And when a position rolls over in counting from (N-index) back to (index+1) and at the same time position "index" swaps with position "N-1-index" (that is to say its mirror column), then we "bump" to the next index and increment the next column.

Thus, in our example of 4 objects, when we reach 4 2 3 1, we increment to 1 2 3 4, but since position 0 (i.e. index=0) rolled over from 4 (N-index) back to 1 (index+1) and at the same time swapped with position 3 (i.e. N-1-index), we bump index to 1 to point to the next column and increment it:

Then, we go back to counting using index 0 as before:

And again counting is complete when the sequence is reversed.  To test for counting completion, we could literally do a comparison to see if the sequence is physically reversed.  But that is a quite a bit of computational effort:

done = 1;
for (i=1; ((i<N) && (done)); i++) if (a[i] >= a[i-1]) done=0;
if (done) exit;

However, because of the mirrored nature of the columns, there is a much more efficient way to determine if we are done.  Once our index value passes the centerline of the mirror, we are done.  That is for 4 objects, once index hits 2 (or larger) we are done.  For 5 objects, since the center column is its own mirror, again once index hits 2 (or larger) we are done.  For 6 objects, it is 3, and so forth.  This can be expressed as:

if (index > ((N/2)-1)) exit;

To summarize this counting algorithm, lets look again at 7 objects.  This time we have 3 paired columns: 0 and 6, 1 and 5, and 2 and 4.  column 3 pairs with itself.  Our counting on column or index 0 goes from 1 to 7.  Counting on column 1 goes from 2 to 6.  And counting on column 2 goes from 3 to 5.  And technically, our self-mirrored column goes from 4 to 4, which means we never increment it.  Let's step through the counting and watch in detail how our column incrementation works:

And that's all there is to it.  Click here if you'd like to download the N-Factorial source code implementation in C.  To use this in a useful application simply replace the printf loop where the current sequence is being printed and replace it with code that performs whatever work you desire to do on the current sequence.

And what if you want to use letters or something else for each entry?  Simple.  All you have to do is use these calculated sequence numbers as indexes into an array of characters or whatever kind of object you wish.

Feel free to use these algorithms freely wherever you see fit.  And please send me any comments that you might have or ideas for additional improvements.  Also, if you have additional counting algorithms that might be useful to others, please send them and I'll post them with this one.  Enjoy!