wood burning stoves 2.0
The moose likes Beginning Java and the fly likes possible combinations of a fixed string Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "possible combinations of a fixed string" Watch "possible combinations of a fixed string" New topic

possible combinations of a fixed string

Praneeth Medukonduru

Joined: Jun 26, 2007
Posts: 5
Hi All,

Kind of a strange problem with a string. Need to replace the char's with * to get all possible combinations, without changing their location.

ex: String = abc

expected result : a** , ab*, *b*, *bc, **c, a*c

as you see the position of the actual characters in the string doesn't change.

any help will he helpful,

Thanks and Regards,
Tom Johnson
Ranch Hand

Joined: May 11, 2005
Posts: 142
Nested for loops are your friend I think. Iterate over the string and for each index reiterate over the other indices replacing each with *. You would skip the index of the one you are on to maintain its position. e.g. if input is "abc" then the first "outer" iteration will use 'a' at index 0. So you iterate over the string again and if inner index == outer index (i.e. 0 in this case) use the original char, 'a'. Otherwise replace each other characters with *. You will need to work out how to do a**, ab*, a*c as part of the inner loop...

<a href="http://faq.javaranch.com/java/UseCodeTags" target="_blank" rel="nofollow">Use Code Tags!!</a>
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
I'd agree with Tom, only instead of a nested for loop you could use a recursive call to a method.

For example:

Note, this is not working code, I just put together some psuedo-code to try an explain the thought process. The logic may not be entirely there either.. hope it helps though.

~Currently preparing for SCJP6
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
A different way to look at it; there are two possible states of any given letter position, either display the letter or display an asterisk. If ou let the 0 state signify displaying the letter, and the 1 state signify displaying an asterisk you have this pattern:

000 => abc
001 => ab*
010 => a*c
011 => a**
100 => *bc
101 => *b*
110 => **c
111 => ***

The $5 question is, what does that pattern represent, and how could you use it to generate your Strings?
[ November 24, 2008: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
So I just tried out the algorithm I was implicitly suggesting and I got:


instead of the sequence I previously posted. Getting the other sequence seems to be a lot more difficult.
Praneeth Medukonduru

Joined: Jun 26, 2007
Posts: 5
@ Garrett Rowe
Can you please post the code you tested for this. It would be really helpful.

and to answer the $5 question

DB stores a comma separated list of values that might be in any of these combinations and the user gives the exact string (ex: abc). Now we have to search the entire DB for records that match that sequence as specified.

Coding any other way was giving a performance bottle neck, as trying to get all records and then figuring out which to eleminate resulted in too many loops. DB holds millions of these records, each with a comma saperated list.

The best solution was to generate all possible combinations (in java) and then fire a select query, this way the results would be quick and gain in performance high.

Thanks for all the replies.

I agree. Here's the link: http://aspose.com/file-tools
subject: possible combinations of a fixed string
It's not a secret anymore!