Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is it possible to generate every possible combination of a 32 character alpha numeric string? If so, how long would it take on today's fast computers?

My lecturer at university said it's impossible, and I thought "nothing is impossible".

Any ideas on how long it'd take and how it'd be done? We're using Java at the moment. I would like to think I can prove him wrong.

share|improve this question
    
@Jack Wilson hacking much? –  P.Brian.Mackey May 16 '11 at 19:44
7  
"Anyone who says 'nothing is impossible' has obviously never tried to staple jello to a tree" –  Jeffrey May 16 '11 at 19:49
2  
@Jeffrey Can you freeze it first? Can you wrap it in a balloon? Can the tree be horizontal? And so on... –  Gary Rowe May 16 '11 at 21:42
1  
@James: First, you sort the list, then you traverse it. It's a mere O(n log n) issue, where n (according to raybritton's comment) is about 2.2E57. It might be possible to do it, using the entire resources of a large cluster of galaxies. –  David Thornley May 17 '11 at 16:59
1  
Just use threads. Everyone knows that threads speed stuff up ;-) –  Karl Bielefeldt Dec 15 '11 at 6:55

7 Answers 7

up vote 10 down vote accepted

It boils down to the math, even if you take pretty crazy values.

Let's say you have an instruction that can generate one 32 character combination in one cycle. Also, you're not storing these combinations so there is virtually no memory access. Finally let's assume that your effective clock speed for these instructions is 2.0 petahertz (ten to the fifteenth cycles per second), which doesn't exist yet outside of the fastest supercomputers on the planet.

The number of 32 character combinations that are alphanumeric with repetition is 36 to the 32nd power. So, 10 to the 32nd power is a much smaller lower bound on this value. To compute this smaller group, you will need 10 to the 17th seconds (combinations / clock speed). There's approximately 32 million seconds in a year, but for this example, we'll take 100 million seconds in a year to make the math easy.

So that leaves us with 10 to the 17th seconds being divided by 10 to the 8th seconds. That means it will take more than 1 billion years for this computation to complete. If you do the math exactly, you'll find that this takes longer than the estimated time we have left before our sun becomes a red giant (5 billion years).

share|improve this answer
    
Forgot to add upper and lowercase. But, even from the example you gave it looks like a waste of time attempting it. Thanks. –  Jack Wilson May 16 '11 at 19:45
5  
Of course, if you divided the work between 1 billion computers, it won't be so bad. Assuming that this task can be split into independent parallel chunks of work.... ;) –  FrustratedWithFormsDesigner May 16 '11 at 19:45
2  
Your math is assuming that your combinations are case insensitive and is only the English version of the Western Latin Alphabet is being used. This results in 36^32, IF we make it case sensitive we end up with 62^32 ~ 2.272 x 10^57 permutations. AND if we add in the complete set of Unicode AlphaNumeric characters, Then I would guess that the heat death of the universe will occur before complementation of the routine. –  mangelo May 16 '11 at 19:51
3  
@mangelo: Or... you will just need MORE than a billion computers working in parallel. ;) –  FrustratedWithFormsDesigner May 16 '11 at 19:59
    
@FrustratedWithFormsDesigner The beauty is that this can actually be done but you would need TONS of PCs :) –  Rig Dec 14 '11 at 21:54

I would suggest trying to generate the first 10000 combinations and measure how long that takes in Java.

Then as a rough estimate compute time needed per combination in your sample size and multiple that times the total number of combinations that are possible. (Maybe even do the math first to determine how many combinations there are because that is the real issue).

share|improve this answer
1  
Oh but everyone knows Java is slow... :-) –  Dan Ray Dec 14 '11 at 20:23

This kind of question shows a very good way to exercise yourself with estimates and orders of magnitude. In all scientific and technical fields, this is a great asset. In fact, it is the number one thing I expect from the people I hire: being able to make educated guesses when no hard data is available.

So, let's get it started:

  • You have a 4 GHz CPU; this means, it does something  4 109 times per second.
  • Now, this something isn't a simple addition, as the processor might perform more than one operation per cycle (for example, think “vectorization”). So, we'll be very generous (after, we want a lower bound on the execution time), and assume that you can iterate (i.e. generate one permutation from another) in one cycle.
  • With lowercase/uppercase, you have 62 alphanumerical characters, so 6232 combinations. Let's, again, be optimistic and say your teacher was talking about all-uppercase: 3632 = 6.3 1049.
  • You divide this by 4 109, and you get roughly 1.5 1040 seconds, which is 5 1032 years, which is… too much.
share|improve this answer

You don't need to generate every possible string - it already exists. If you're searching for a particular string, you don't need to search. It exists. If you want to store it, it's already stored - it takes 0 bytes to store and 0 time to fetch.

In other words, the result already exists and is cached in the fabric of reality, so generating the result is actually the fastest operation possible.

It's a bit like asking someone to write a sort algorithm that sorts all integers from 1 to 1000, given that every one is unique. You don't need to sort at all.

share|improve this answer
1  
This is a great comment, but has the unfortunate side effect that I am now looking to use the phrase "the result is cached in the fabric of reality" when trying to explain to someone why I don't need to do any work :) –  nlawalker Dec 14 '11 at 19:22
    
Heh, I suppose I will start to use that more myself! :D –  Kevin Hsu Dec 14 '11 at 19:51
    
Right. Generating the sequence as an Iterator is fast. Iterating thru the sequence up to the end, THAT is slow. And ... well ... stupid. –  Florian F Sep 22 at 15:24

Given that there are 62 alphanumeric characters, the amount of possible combinations equals 62^32 = 2.27e+57. Also known as .. huge!

Fun facts: storing this using 8 bits per character would take up 1792810956021776957992730108.0124 Geopbytes

As jzd states, try benchmarking the time it takes to generate a certain amount of them. From this you can calculate an average time per combination, multiply this with the amount of possible combinations and you'll have the time required.

share|improve this answer

Of course its possible. Or is your lecturer suggesting there's some letter/number combination that cant be represented in a 32 character string?

is it Feasable... now thats an entirely different question. If you were able to harness most of the machines on the internet, you could probably do it in a time span small enough that the end result was still relevant.

share|improve this answer

If we think outside the box for a while, this sort of combinatorial explosion is what quantum computers are good at. If you have 64 symbols (6 bits) and a string length of 32, you would need a 6*32=192 bit quantum computer to solve it "instantly", depending on what you actually want to do with the strings - are you searching for one with a hash that matches a given hash value?

Incidentally, starting just a few days ago, you can order a 128-bit quantum computer from D-wave (hotly contested if it really is quantum computation, though). That is still not enough, since you lack 64 bits, which means that you would need to run your algorithm 2**64 times, which is still waaay too much.

192 bits will probably come along sooner or later though. Then you'll be able to show him ;)

share|improve this answer

protected by gnat Sep 22 at 15:41

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.