# Printing out the combinations of a given string

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.

Thanks in advance

Phani

Sheriff

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.

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

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.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Originally posted by Eugene Kononov:

Here is an excercise for you guys: what is the probability that this program willnotproduce 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)?

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

**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 ]

Sheriff

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.

"I'm not back." - Bill Harding, *Twister*

**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 ]

Sheriff

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 ]

"I'm not back." - Bill Harding, *Twister*

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

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.

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

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Sheriff

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:

"I'm not back." - Bill Harding, *Twister*

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.

*Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction.* - Ernst F. Schumacher

Sheriff

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

"JavaRanch, where the deer and the Certified play" - David O'Meara

It is sorta covered in the JavaRanch Style Guide. |