CODEWITHSUNDEEP
python-3.x
Lzypenguin
Lzypenguin

Reputation: 955

I am trying to finding every possible combination of adding a character to a string

I am trying to get every possible combination of adding a character to a string. For instance:

Lets say I have the string: abcdefg1234567890

I want to find every possible combination of that with the characters in the EXACT SAME order, but adding "-" in between each character. So i want my responses to include everything between:

a-bcdefg1234567890 AND ab-cdefg1234567890 AND abc-defg1234567890

Etc, as well as: a-b-c-d-efg1234567890 AND abc-defg-1234-5678-9-0

My code already take the string and starts adding "-" bewteen characters, and then once it gets to the end, it stores that value and adds more characters from left to right. This this will give me every combination with "-" on the right side, but will not include things like:

a-b-cdefg1234567890

because after the 1'st hypen gets to the end it stays there, and starts adding more from left to right.

Any help is appreciated.

Thanks

Upvotes: 1

Views: 344

Answers (1)

Duncan C
Duncan C

Reputation: 131471

This is a coding logic problem. It doesn't have much to do with the programming language. I was looking in another SO and accidentally wound up in the Python SO instead. I don't know Python, but I can tell you how to solve the problem algorithmically.

If you want every possible combination of "dash-between-characters" and "no-dash-between characters" you'd going to output 2^(chars-1) possible strings. (If there are 4 characters in your string, there are 3 spaces between those characters.)

You have a 17-character string, so there will be 2^16 possible combinations, or 65536 different strings. That's a LOT of output strings.

You need to write code that counts from 0 to 2^(chars-1). For each value, you'll generate one of your possible output strings. The bits of that count will tell you which character pair should get a dash inserted there, and which should not.

To do that, write code that loops through every bit in the binary of the count and if the bit is 1, adds a dash to the output at that position, and if the bit is 0, does not add a dash at that position.

Pretend you only have 4 characters: 1234. There are 3 spaces for dashes, 1-2-3-4.

Say we name each of those dash positions as A, B and C:

1A2B3C4

Now lets say we assign a 1 to each letter if it gets a dash, and 0 to the letter if it does not.

Writing it out putting spaces in place of the dashes so you can see the patterns:

ABC     A B C
000    1 2 3 4
001    1 2 3-4
010    1 2-3 4
011    1 2-3-4
100    1-2 3 4
101    1-2 3-4
110    1-2-3 4
111    1-2-3-4

Each time you add another character, you add another between character spot that could contain a dash or not, so you double the total number of possible output strings.

Note that the patterns of 0s and 1s in my ABC values are the bit patterns you get when you count in binary.

EDIT:

Write 2 nested loops:

Outer loop: Loop from 0 to `2^(char_count - 1)`. Let's call that value dashBits.

//Each value of dashBits will generate one of your possible output strings (in your case, one of 65536 output strings.

set outputString to an empty string.

Inner loop: Loop from left to right of the input string

   Append the current input character of your input string to the output.
   Look at the 0th bit of dashBits. If it's 1, append a dash to your output. If it's 0, don't do anything.    
   Shift dashBits 1 bit to the right.

Upvotes: 2

Related Questions