# Printing out the combinations of a given string

Phani Kumar
Greenhorn
Posts: 3
Hello all.
Can anybody tell me the required logic to printout all the combinations of a given string? I have to print 1. all combinations and 2. Only unique combinations.
Phani

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I can't tell what this means. "All combinations of a given string"? Can you give an example? Like, here's a string: "taco". What are all combinations of this string?

Phani Kumar
Greenhorn
Posts: 22
Means all possible combinations with the characters of the string i.e. for instance if you take string "abc", you have to print abc, acb, cab,bca etc.

Joel McNary
Bartender
Posts: 1840
I did this a while ago in C, but keep in mind that for a string of 7 unique characters, there are 5,040 different combinations! Granted, that lessens once you introduce non-unique characters ('eeeeeee' still has 5,040 permutations, but only 1 that counts )
Let's see if I can translate my C to java:

This isn't the greatest style-wise, but it's pretty-much a direct copy from my C code. You are probably better off creating char[]s instead of putting everything into Lists.

John Smith
Ranch Hand
Posts: 2937
I've got the dumbest and shortest solution (but it works). I am thinking of putting in in my future book, "Java: How Not To Program":

Here is an excercise for you guys: what is the probability that this program will not produce the correct output?
Eugene.

Michael Morris
Ranch Hand
Posts: 3451

I am thinking of putting in in my future book, "Java: How Not To Program":

I'll write the Forward for it if you'll give me an autographed copy.

Joel McNary
Bartender
Posts: 1840
Originally posted by Eugene Kononov:

Here is an excercise for you guys: what is the probability that this program will not produce the correct output?
Eugene.

Well, if the initial string has > 7 unique characters, 100%, since you are only performing 1000 shuffles and there are 5040 answers to the 7 character string
Other than that, I can't tell you. There are 6 answers for three-character strings, 24 for four-character strings, 120 for five-character strings, and 620 for six-character strings. Off hand, I'd say that you stand a good chance of getting the correct answers up to 5-character strings, but the 6-character strings you probably only have about a 40-50% chance of success.
I'm no stastician, though, so this is only a guess.
Another question: how many random shuffles would you have to do to get all the answers to the string "victory" (7 unique letters)?

John Smith
Ranch Hand
Posts: 2937
JM: Well, if the initial string has > 7 unique characters, 100%, since you are only performing 1000 shuffles and there are 5040 answers to the 7 character string
Right, but I offered this exercise for that exact code and input that I posted, -- the string is "abcc" and there are exactly 1000 shuffles.
MM: I'll write the Forward for it if you'll give me an autographed copy.
I'll have you write a chapter on the private inheritance, with Cindy.
Eugene.
[ April 25, 2003: Message edited by: Eugene Kononov ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Phani - just to be clear, what you describe aren't "combinations", they're "permutations". Combinations would ignore order - the possible combinations of "abc" would be
a
b
c
ab
ac
bc
abc
Anyway though - for your problem, you do want only the three-letter permutations for abc, right? You can't omit letters like I did for the combinations? Probably not - just making sure.
Doing a JavaRanch search on "permutations" yields several past discussions. You might look at these in particular:
http://www.coderanch.com/t/369176/java/java/Loops
http://www.coderanch.com/t/391299/java/java/help-permutation
I swear there were some other good discussions of this here, but couldn't find them.
Eugene - hmmm, interesting question. I don't have a good complete answer offhand, but I will note that it seems to be equivalent to the following problem: if you generate a random number from 1-12 1000 times, what is the probability that at least one number in 1-12 will never be generated?
Wouldn't be too difficult to get an empirical answer to this by running some quick simulations, but I assume you're hoping for an analytic solution. Memories of probability theory... fuzzy... will think more though.

John Smith
Ranch Hand
Posts: 2937
JY: Wouldn't be too difficult to get an empirical answer to this by running some quick simulations, but I assume you're hoping for an analytic solution. Memories of probability theory... fuzzy... will think more though.
Why don't we separate the responsibilities, Jim. You think of an analytical solution and I'll run some Monte-Carlo code to validate it. But for a random guess, I will say that the probability is around 12/1000, or 1.2%.
[ April 25, 2003: Message edited by: Eugene Kononov ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Looks more like 1.95E-37. Otherwise known as "zero" for most practical purposes. Though there's still a decent chance of an error somewhere in my method. I've got an analytic formula, but it's complex enough that it was easier to write a program to evaluate it. I had no idea that BigInteger and BigDecimal were so ugly to use. Anyway, here's the output, given several possible inputs. M is the number of possible outcomes for each trial (12 for the number of permutations for "abcc") and N is the number of trials (1000 in Eugene's code). Then P is the probability that at least one of the M outcomes will never be reached in all N trials.

The first three lines were inserted as a reality check - it's easy to see that if you flip a coin twice, there's a 50% chance of either no heads, or no tails. For three flips, it's .25, and for four flips, it's .125. So I was happy to see my solution conform to this. For the other numbers, I'll let Eugene do the Monte Carlo approach and see what we get...
[ April 25, 2003: Message edited by: Jim Yingst ]

John Smith
Ranch Hand
Posts: 2937
Jim Yingst:
M: 12N: 20P: 0.9486463353447393
M: 12N: 30P: 0.6408547968197952
M: 12N: 40P: 0.3267838198555476
M: 12N: 50P: 0.14766508956076288
M: 12N: 60P: 0.06367937077207302
M: 12N: 70P: 0.026974488760632742
M: 12N: 80P: 0.011348267584557531
M: 12N: 90P: 0.004761689462457003
M: 12N: 100P: 0.0019959598731472718

I verified it for this range with my Monte-Carlo code, here is what I got:
M: 12N: 20P: 0.948639
M: 12N: 30P: 0.641403
M: 12N: 40P: 0.326897
M: 12N: 50P: 0.147323
M: 12N: 60P: 0.063895
M: 12N: 70P: 0.026818
M: 12N: 80P: 0.011308
M: 12N: 90P: 0.004803
M: 12N: 100P: 0.002041
Very remarkable, Jim! Would you share your analytical solution with us?
I guess the most surprising result is the 1.9526317946955E-37 probability that my original code will produce an incorrect result. According to my estimate, if every person on this planet ran this program continuously, one run per second, it would take 10^7 trillion years before it would produce bad result.
Here is my Monte-Carlo code that I used to validate Jim's numbers, if anyone is interested:

Eugene.

Michael Morris
Ranch Hand
Posts: 3451
EK: I'll have you write a chapter on the private inheritance, with Cindy.
I'm not so sure Cindy would agree, seein' as how I got my panties in a wad over her post.

John Smith
Ranch Hand
Posts: 2937
I'm not so sure Cindy would agree, seein' as how I got my panties in a wad over her post.
Look at her, -- can she refuse an offer from a Texan?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
OK, cool. Here's what I did:
Let M = number of possible outcomes for one trial = 12. Think of one trial as generating a single random int in range 1-12.
Let N = number of trials = 1000. We're going to generate 1000 random numbers in range 1-12, and count up all the different ways this can happen.
Let C(all) represent the number of possible outcomes for all trials. This is
C(all) = M^N (where ^ is "to the power of")
Let C(i) represent the number of outcomes in which when you look at the numbers from all trials, there are i different numbers which are present, and M-i other numbers which do not appear in any trial for a given outcome. 1 <= i <= M.
We're interested in C(M) (that is, C(12)) in particular. We have
C(all) = C(12) + C(11) + C(10) + ... + C(1)
C(12) = C(all) - C(11) - C(10) - ... - C(1)
C(12) = 12^1000 - C(11) - C(10) - ... - C(1)
Now what about C(11)? Imagine we pick one of the twelve numbers as "off limits" and calculate C(11) as we did C(12) previously. This leads us to
C(11) = 12 * 11^1000 - C(10) - C(9) - ... - C(1)
The initial 12 comes from the fact that there were 12 numbers we could've declared off limits. Similarly, if we pick two different numbers and declare them off limits, we get
C(10) = ((12 * 11) / 2 ) 10^1000 - C(9) - C(8) - ...
or for three numbers off limits...
C(9) = ((12 * 11 * 10) / (2 * 3) ) 9^1000 - C(8) - C(7) - ...
The 12 * 11 * 10 is the number of ways we could pick three different numbers, divided by 2 * 3 since the order we pick them in doesn't matter here. The general term is
C(i) = M! / (i! * (M-i)!) - C(i-1) - C(i-2) ...
Eventually though we get to
C(1) = M
Now we can substitute everything back in to solve for C(12):
C(12) = 12^1000 - 12*11^1000 + (12*11/2)*10^1000 - (12*11*10/(2*3))*9^1000) ... + 12*2^1000 - 12
Note alternating sign.
Once we have C(12), we can calculate probability of failure (at least one numbers is not represented in any trial) as
F = (C(all) - C(12)) / C(all)
Whew! So, here's the code to calculate:

Michael Morris
Ranch Hand
Posts: 3451

Look at her, -- can she refuse an offer from a Texan?

I'm afraid she might try to give me a vasectomy with that six-shooter.

Cindy Glass
"The Hood"
Sheriff
Posts: 8521
Originally posted by Michael Morris:
I'm afraid she might try to give me a vasectomy with that six-shooter.

No, I don't think that I can get at your private parts .

I am thinking of putting in in my future book, "Java: How Not To Program":
I have LOT'S of potential input to that book! .