# Algorithm all possible permutations of letters

Tempora Telora
Ranch Hand
Posts: 83
Anyone know the algorithm or can anyoen give me a link to the algorithm that will generate all possible combinations of letters? Up to lets say 20 letters or so?

ie aec
...
...
...
zzzzzzzzzzzzzzzzzzzzzzzzzzz

Thanks guys,
Randy

Keith Lynn
Ranch Hand
Posts: 2409
I think you can come up with an algorithm if you look at how you would generate the combinations if they were written on a piece of paper.

Tempora Telora
Ranch Hand
Posts: 83
Understandable. But if someone does know a link or can post the code it would be greatly appreciated.
[ June 06, 2006: Message edited by: Randy Tatham ]

marc weber
Sheriff
Posts: 11343
Originally posted by Randy Tatham:
...all possible combinations of letters? Up to lets say 20 letters or so? ...

Do you have an idea of how many combinations to expect?

I'm asking for 2 reasons: First, I think you're about to write some code that will appear to take forever (if it doesn't run out of memory). Second, the approach to calculating this quantity provides a hint at the algorithm for generating these combinations.

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
For us music majors, what's the definition of permutations? If we take all permutations of AB is it

A
B
AB
BA

or do we count

AA
BB

or what?

marc weber
Sheriff
Posts: 11343
Originally posted by Stan James:
For us music majors...

A la Schoenberg?

Well, under a traditional definition, "a permutation is an ordered list without repetitions, perhaps missing some elements." Using your example, this would be A, B, AB, and BA. However, under a more formal definition, "a permutation is an ordered sequence containing each symbol from a set once and only once." So this would be AB and BA, but not A or B. In contrast, "a combination is an un-ordered collection of unique elements." (Ref: Wikipedia - Permutation and Wikipedia - Combination.)

Note that under either definition, the original poster's example of "zzz..." would not be allowed. So I do think we need more clarification on what exactly the goal is.
[ June 06, 2006: Message edited by: marc weber ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[this is a direct response to Stan, before marc butted his head in.]

And for non-music majors , note that permutations and combinations are two different things, not to be confused.

Regardless, I strongly recommend trying to answer Stan's post here first. List all the results you expect to find. Then move to something slightly bigger, like say, using the letters A, B, C and listing all permutations / combinations / whatever that are no longer than 3 characters. See if you can find a pattern along the way, or at least refine the rules of what you're asking for.
[ June 06, 2006: Message edited by: Jim Yingst ]

marc weber
Sheriff
Posts: 11343
Originally posted by Jim Yingst:
[this is a direct response to Stan, before marc butted his head in.] ...

Okay. With that cleared up, can we talk Thelonious Monk now?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Sure. Though sadly, I haven't gotten around to picking up the recently-discovered Carnegie Hall recording with Coltrane. Otherwise, fire away...

Sheriff
Posts: 14691
16
Hi guys, we were taking about thread hijacking recently, and I smell one here That would be cool to go back to the main topic, if it's not already closed.

Steve Fahlbusch
Bartender
Posts: 605
7
I do have to say that the newly released monk is a great recording. Talk about combinatorial patterns!!!

Ken Blair
Ranch Hand
Posts: 1078
Assuming you only permit the 26 letters of the alphabet and it's case insensitive you're looking at something like 19,928,148,895,209,409,152,340,197,376 possible combinations. Where exactly do you hope to store all the combinations you generate? Are you going to print them out? Even were you to print out one billion generated combinations every second it would take some 630+ billion years to print them all out. By contrast, our sun will die in about 5-6 billion years, good luck with that.

I think marc is right, you're about to write some code that will end prematurely when our sun dies.

Sheriff
Posts: 14691
16
Where exactly do you hope to store all the combinations you generate? Are you going to print them out?

Maybe on toilet paper, that would make a great record in the Guiness book

Jim Yingst
Wanderer
Sheriff
Posts: 18671

See, Satou? It is on topic!

Anyway, I figure when Randy gets back to us with more specifics, and hopefully some further thoughts, then we can help him along some more. Discussing solutions for all possible interpretations of the problem without some feedback seems a bit counterproductive to me.

But if marc was actually planning an extended discourse on Monk, perhaps MD would be more appropriate. Ah, well...
[ June 06, 2006: Message edited by: Jim Yingst ]

marc weber
Sheriff
Posts: 11343
Originally posted by Jim Yingst:
... But if marc was actually planning an extended discourse on Monk, perhaps MD would be more appropriate...

Yeah, I was thinking of a Monk post in MD, even if it's not quite an extended discourse. Thanks for mentioning that newly discovered recording! Coltrane on "Crepescule With Nellie" could be... Crazy.

Campbell Ritchie
Sheriff
Posts: 50182
79
Do you have an idea of how many combinations to expect?

This many: 19928148895209409152340197376. If I have copied it from my calculator program correctly.

CR

Ken Blair
Ranch Hand
Posts: 1078
Originally posted by Campbell Ritchie:

This many: 19928148895209409152340197376. If I have copied it from my calculator program correctly.

CR

Which happens to be the exact same number I posted four replies ago.

Campbell Ritchie
Sheriff
Posts: 50182
79
I really ought to read posts properly, shouldn't I? Sorry

Henry Wong
author
Marshal
Posts: 21496
84
I guess one way to do it would be recursively... The algorithm would be...

The method should take a prefix string and the number of letters to add.

If there are no letters to add, then add/print the prefix string somewhere.

If there are letters to add, then use a loop to recursively call the method, with a prefix of the previous prefix plus one character (obviously, each call will generate 26 recursive calls), and one less character to add.

Henry

fred rosenberger
lowercase baba
Bartender
Posts: 12196
35
But if someone does know a link or can post the code it would be greatly appreciated.

Randy, that's not how we like to work around here. we don't post solutions for people's homeworks. We're glad to look at the code YOU'VE written, make suggestion, answer questions, etc.

But we don't hand you the answer to what is something you're supposed to do yourself.

You might want to check your school's code of conduct and ethics rules about handing in someone else's work...

Tempora Telora
Ranch Hand
Posts: 83
sorry i havent gotten back to you guys..

fred lol this isnt homework my man.
A. Why would a teacher give out a problem that would take days to go through all the combinations?

Granted fred your probably not going to believe me but I finished college last semester. If you want I will send you via email my transcript lol.

What I am doing this is taking it into a generator to retrieve all possible values in the generator. I expect this to run multiple days. Yes it will be a memory hog but I have a computer set aside to run it. Once I retrieve each data I will be storing it into a database.
[ June 07, 2006: Message edited by: Randy Tatham ]

Ken Blair
Ranch Hand
Posts: 1078
Originally posted by Randy Tatham:
sorry i havent gotten back to you guys..

fred lol this isnt homework my man.
A. Why would a teacher give out a problem that would take days to go through all the combinations?

Granted fred your probably not going to believe me but I finished college last semester. If you want I will send you via email my transcript lol.

What I am doing this is taking it into a generator to retrieve all possible values in the generator. I expect this to run multiple days. Yes it will be a memory hog but I have a computer set aside to run it. Once I retrieve each data I will be storing it into a database.

[ June 07, 2006: Message edited by: Randy Tatham ]

Have you actually read the previous replies? This isn't going to take days, this is going to take years. Store them in a database? I'd like to see that. You're talking about 19928148895209409152340197376 20 character strings here. Even assuming each character is only one byte you're talking about 398562977904188183046803947520 bytes of data. Where do you plan on finding a database that can hold 371,190,698,728,140,614,039 GB of data?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Though if you're willing to limit the solution set to a smaller length than 20, it may be much more possible to solve this in your lifetime.

Ken Blair
Ranch Hand
Posts: 1078
Or limit the valid characters. I don't see why anyone would want a database full of all possible permutations, what is it you hope to accomplish?
[ June 07, 2006: Message edited by: Ken Blair ]

fred rosenberger
lowercase baba
Bartender
Posts: 12196
35
ok, you've finished college, and need help doing this. But my point is still valid. we don't hand out code here. Most of us are professional programmers, and we'd be happy to sell you our services, if that's what you want. or you can try here.

This site is for helping people LEARN to be java programmers. that is not accomplished by giving you the answer. it's done in a dialogue, where you ask specific questions, and people guide you to discovering the answers.

Now, reading the previous posts, you'll learn that your original post was a) vague, b) incomplete, and c) WAY to large.

So, answer some of those questions, and we're happy to help.

if all you want is the answer/code, see above.

Ryan McGuire
Ranch Hand
Posts: 1078
4
Originally posted by Ken Blair:

Where do you plan on finding a database that can hold 371,190,698,728,140,614,039 GB of data?

Maybe he's working on a new compression algorithm.

I wonder how well a HasMap would perform, using the standard String hashcode(), on 19 bazillion keys.

marc weber
Sheriff
Posts: 11343
Originally posted by Ken Blair:
Which happens to be the exact same number I posted four replies ago.

That's assuming each "permutation" is no less than 20 characters and might contain duplicates. If we allow possibilities of less than 20 characters, then the quantitiy increases to 20725274851017785518433805270. On the other hand, if we don't allow duplicates, then the quantity drops to either 651380959204220218834276 or 560127029342507827200000, depending on whether possibilities of less than 20 characters are allowed.

marc weber
Sheriff
Posts: 11343
Originally posted by Jim Yingst:
...if marc was actually planning an extended discourse on Monk, perhaps MD would be more appropriate...

Not an extended discourse. Just a little rumination.