# How many ways are there to delete characters from a 10-character string?

I'm trying to show why an algorithm is inefficient. The following isn't exactly how the algorithm works, but it is a good approximation.

Say I have the $$10$$-character string "$$0123456789$$". I can remove characters from the string by replacing them with an empty space. Here are a few examples:

"0123456789"
"0 23456789"
"0123 56789"
"  2  56 89"
"012       "
"0         "
"          "


If I wanted to iterate through every possible combination, how many iterations would it take? A general solution would be nice because the program actually works on data that has an arbitrary number of elements.

• As for actually implementing this, you might consider looping over the numbers $0$ to $2^n-1$ and interpreting the numbers in binary, then interpreting each as an array of booleans for either including the character vs including a whitespace. – JMoravitz Nov 1 '19 at 14:55
• A recursive method is to first make a list of strings holding "0" or " " (two strings) then copy these twice, first with a trailing "1" and second with a trailing " ", then repeat the copying process with 2,3,4,5...9 - You could do that using a recursive function. From a software engineering perspective, that's probably not the optimum solution. – Cato Nov 1 '19 at 15:00

Another way of thinking about this, if you have a computer science background is to think about writing your string but with a $$1$$ where you keep the original letter and a $$0$$ where you discard it.

Let's take a string of length $$3$$ to illustrate my meaning, "abc". First we convert each possible modification into our new representation:

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


If we then consider these new representations to be binary numbers then we have

abc  -> 111 = 7
-> 000 = 0
a    -> 100 = 4
b   -> 010 = 2
c  -> 001 = 1
ab   -> 110 = 6
a c  -> 101 = 5
bc  -> 011 = 3


Hopefully you can see that we have every number there from $$0$$ to $$7$$, that is to say we have $$8$$ possible modifications of our string.

We know that $$8=2^3$$ and our string has length $$3$$, so we can guess that for a string of length $$n$$ that we would expect to have $$2^n$$ modifications. I will leave it to you to convince yourself that this is in fact the case.

HINT:

Say your string has $$n$$ characters. If I understand your question correctly you are interested in how many different ways there are to delete characters.

If it is so think as follows:

The first character is either deleted or not, this gives $$2$$ possibilities. The second character is either deleted or not, this gives $$2$$ more possibilities and since these are "independent" you use rule of product to get $$2\cdot 2$$ different outcomes.

Following this logic for a string of length $$n$$ there are $$2^n$$ different ways.

Hope this helped