0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – JMoravitz Nov 1 '19 at 14:55
  • $\begingroup$ 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. $\endgroup$ – Cato Nov 1 '19 at 15:00
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.