user2000189 - 1 year ago 60
Java Question

# Form 2^n combination string

From a given string, to form different set of combination by considering the formula 2^n (2 power n).

For example consider the below example string (AA%0%0%). Where "%" is optional value, hence "%" can be added in string combination or can be removed from string combination, hence posibility of different string combinations as below.

Example String:
AA%0%0% {% index positions are [2,4,6]}

Different possible combination for the example string : (2^n, where n=3 (because "%" count is 3) equals 2^3 = 8 combinations)

For easy understanding, i am replacing "%" with "*" in below combination.

``````1. AA*0*0* [no % omitted]
2. AA*0*0  [index 6 % omitted]
3. AA*00*  [index 4 % omitted]
4. AA0*0*  [index 2 % omitted]
5. AA*00   [index 4,6 % omitted]
6. AA0*0   [index 2,6 % omitted]
7. AA00*   [index 2,4 % omitted]
8. AA00    [index 2,4,6 % omitted]
``````

Now the question is, number of "%" string will vary according to user input, hence, each time to form this combination, i want to write a program in java, which will automatically for this combination according to 2^n formula. Is there any already existing algorithm available to do so? kindly suggest.

Edited:

For better understanding, i am giving different index which, can be formed from 3 count (2^3 = 8). This depends on index position, for example, % index are as 2,4,6 means

1. [2]

2. [4]

3. [6]

4. [2,4]

5. [2,6]

6. [4,6]

7. [2,4,6]

8. [No index (%) removed all characters available]

You can write a recursive implementation of this. The idea is to check in the provided string if the `character` at index `i` (which you can pass as paramter to the function) is `%` or not, if it is, then take two actions:

• Make a recursive call by not omitting the character at index `i` (You need to make this call anyway, in both cases, i.e. whether the character at `i` is `%` or not)
• Make a recursive call by omitting the character at index `i` (which is `%`, which we have checked)

And when `i` reaches at the end of the string, you've got yourself a combination. (Since you've done this many recursive calls, so you'll find all of the combinations)

Following, I'll implement using the above idea:

``````public static void allCombinations(String s, int i){
if (i < s.length()){
// Make a recursive call without removing the character
allCombinations(s, i + 1);

if (s.charAt(i) == '%'){
// Remove character at index i and make a recursive call with new string
String temp = s.substring(0, i) + s.substring(i + 1);
allCombinations(temp, i);
}

}
else{
// print the combination found.
System.out.println(s);
}
}
``````

and call this recursive implementation by passing `0` as the starting index (because you need to start from `0`) like this: `allCombinations("AA%0%0%", 0);`

EDIT

here, you can find the implementation tested with the provided string (`AA%0%0%`) on ideone

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download