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

Question

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.

Answer 1

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.

Answer 2

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