wood burning stoves 2.0*
The moose likes Java in General and the fly likes Algorithm all possible permutations of letters Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Algorithm all possible permutations of letters" Watch "Algorithm all possible permutations of letters" New topic
Author

Algorithm all possible permutations of letters

Tempora Telora
Ranch Hand

Joined: Jun 20, 2005
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

Joined: Feb 07, 2005
Posts: 2367
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.

You could start with 2 letters and see a pattern.
Tempora Telora
Ranch Hand

Joined: Jun 20, 2005
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

Joined: Aug 31, 2004
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.


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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?


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
marc weber
Sheriff

Joined: Aug 31, 2004
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

Joined: Jan 30, 2000
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 ]

"I'm not back." - Bill Harding, Twister
marc weber
Sheriff

Joined: Aug 31, 2004
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

Joined: Jan 30, 2000
Posts: 18671
Sure. Though sadly, I haven't gotten around to picking up the recently-discovered Carnegie Hall recording with Coltrane. Otherwise, fire away...
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  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.


[My Blog]
All roads lead to JavaRanch
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 557
    
    7

I do have to say that the newly released monk is a great recording. Talk about combinatorial patterns!!!
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
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.
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  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

Joined: Jan 30, 2000
Posts: 18671
[Steve]: Talk about combinatorial patterns!!!

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

Joined: Aug 31, 2004
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

Joined: Oct 13, 2005
Posts: 38075
    
  22
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

Joined: Jul 15, 2003
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

Joined: Oct 13, 2005
Posts: 38075
    
  22
I really ought to read posts properly, shouldn't I? Sorry
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18546
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11170
    
  16

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...


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Tempora Telora
Ranch Hand

Joined: Jun 20, 2005
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

Joined: Jul 15, 2003
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

Joined: Jan 30, 2000
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

Joined: Jul 15, 2003
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

Joined: Oct 02, 2003
Posts: 11170
    
  16

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

Joined: Feb 18, 2005
Posts: 1006
    
    3
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

Joined: Aug 31, 2004
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

Joined: Aug 31, 2004
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Algorithm all possible permutations of letters
 
Similar Threads
The BarTenders Kids
WA #1.....word association
Unique 8-length chars algorithm
Looking for a leg up on an Anagram algorithm
Creating PDFs in a web app