Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# possible combinations of a fixed string

Praneeth Medukonduru
Greenhorn
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.

Thanks and Regards,
Praneeth

Tom Johnson
Ranch Hand
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...

Brian Legg
Ranch Hand
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.

Garrett Rowe
Ranch Hand
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 ]

Garrett Rowe
Ranch Hand
Posts: 1296
So I just tried out the algorithm I was implicitly suggesting and I got:

abc
*bc
a*c
**c
ab*
*b*
a**
***

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

Praneeth Medukonduru
Greenhorn
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.

Regards,
Praneeth