How to get all combinations of a string with fixed character position?

Question

I need to find a way to produce all combinations of a string with a particular character to always display in PHP.

For example, given a string 'ABCD', and I want to get all combinations of the string with the character 'B' present, I want to get:

array(' B ', ' BC ', ' BCD', ' B D', 'AB ', 'ABC ', 'AB D', 'ABCD')

The missing characters are replaced with spaces. Anyone have any ideas?

Answer 1

It's easy if you think of each letter in the string being either "on" or "off" - like a bit in a binary number. In fact, you can represent it as such.

So think of your string as a four bit number, which can be anything from 0b0000 = 0 = "" to 0b1111 = 15 = "ABCD". Then you can just run through all the numbers from 0 to 15, and find the respective "permutation" by seeing what bits are set.

For example, "permutation" 6: 0b0110 -> " BC "

Hope that helps!

PS: If this is homework, you should tag it as such - it's a bit of a faux pas around here not to.

PPS: Your "permutations" are actually "combinations." Linked to Wikipedia just in case you're curious.