Fun with recursion

General PHP Help
#1

Hi everyone.

I’m trying to figure out some code that will take a string, for example ABCDE

One of the arguments should be the number of recursions.

If the number is 0, then the string should be returned as is (obviously, that’s pretty easy to implement).

However, with one recursion, an array with the following values should be returned.
[ 'ABCDE', ' BCDE', 'A CDE', 'AB DE', 'ABC E', 'ABCD ', ]

I’ve added spaces just to make it clear where the letters are omitted, but they shouldn’t be there in the returned strings.

If the number of recursions is set to 2, then we should get the above array as well as the following:
[ ' CDE', ' B DE', ' BC E', ' BCD ', 'A DE', 'A C E', 'A CD ', 'AB E', 'AB D ', 'ABC ', ]

Essentially, the second set of results can be created with the following loop.
`
$str = ‘ABCDE’;
$strArr = [];
$tmpStr = ‘’;
for ($i = 0; $i < strlen($str); $i++) {
for ($c = 0; $c < strlen($str); $c++) {
if ($i !== $c) {
$tmpStr …= substr($str, $c, 1);
}
$strArr[] = $tmpStr;
}
}

And the third set of results can be created like this:

for ($i = 0; $i < strlen($str); $i++) {
for ($c = 0; $c < strlen($str); $c++) {
for ($j=0; $j < strlen($str); $j++) {
if ($i !== $c && $j !== $c) {
$tmpStr …= substr($str, $c, 1);
}
$strArr[] = $tmpStr;
}
}
}

It goes without saying how to do the forth, fifth and so on. I figured the solution must involve recursion.

I know this question looks a bit ‘homeworky’, but I promise it’s not. This is for a database project I am making for indexing words in a way that will make them easier to search in a specific way. I’d appreciate it if anyone could help here. I’ve made recursive functions before, but this one is driving me crazy. I’ve been working on it for hours and I just can’t get it right.

Many thanks in advance.

#2

Wow, a PHP Help forum that doesn’t allow you to format code correctly. Unfortunately, I am head out to a prior arrangement, but I will look into getting the code hosted somewhere else that will make it clearer when I return.

#3

You can format code correctly; use three backticks to start and end your snippet, or use four spaces at the start of each line.

You could solve this with recursion, but it’s probably more faff than you need. You can just record your last iteration and iterate as many times as required, like so:

function combinations(string $word, int $num_of_removals): array
{
    $out = [$word];
    $seed = [$word];

    for ($i=1; $i<=$num_of_removals; $i++) {
        $new_subwords= [];
        foreach ($seed as $subword) {
            $subword_length = strlen($subword);
            for ($j=0; $j<$subword_length; $j++) {
                $new_subwords[] = substr_replace($subword, '', $j, 1);
            }
        }

        // we only want unique combinations
        $unique_new_subwords = array_unique($new_subwords);

        $out = array_merge($out, $unique_new_subwords);
        $seed = $unique_new_subwords;
    }

    return $out;
}

This gives you the following results:

combnations('ABCDE', 0);
[
    "ABCDE"
]

combinations('ABCDE', 1);
[
    "ABCDE",
    "BCDE",
    "ACDE",
    "ABDE",
    "ABCE",
    "ABCD"
]

combinations('ABCDE', 2);
[
    "ABCDE",
    "BCDE",
    "ACDE",
    "ABDE",
    "ABCE",
    "ABCD",
    "CDE",
    "BDE",
    "BCE",
    "BCD",
    "ADE",
    "ACE",
    "ACD",
    "ABE",
    "ABD",
    "ABC"
]
#4

use [ code ] [ /code ] tags

(no spaces obviously)

#5

Aah. That’s handy. I was just going by what was provided within the editor. Now I know I can do more. Thank you. :smile:

#6

That’s awesome, thank you! The best I came up with using recursion was this:

function combinations($str, $numWildcards=0, $startPos=0)
{
    $resArr = [];
    $strLen = strlen($str);
    
    if ($numWildcards > 0) {
        for (; $startPos<$strLen+1-$numWildcards; $startPos++) {
            $prefix = ($startPos > 0) ? substr($str, 0, $startPos) : '';
            $suffix = substr($str, $startPos+1);

            foreach (combinations($suffix, $numWildcards-1, 0) as $suffix) {
                $resArr[] = $prefix.$suffix;
            }
        }
    } else {
        $resArr[] = $str;
    }

    return $resArr;
}
combinations('ABCDE', 0);
[
    "ABCDE",
]
combinations('ABCDE', 1);
[
    "BCDE",
    "ACDE",
    "ABDE",
    "ABCE",
    "ABCD",
]
combinations('ABCDE', 2);
[
    "CDE",
    "BDE",
    "BCE",
    "BCD",
    "ADE",
    "ACE",
    "ACD",
    "ABE",
    "ABD",
    "ABC",
]

It works, but it needs the ability to store multiple calls all in one like yours. I think you’re right though. It was more faff than necessary. At least now, thanks to you, I have a working solution that I can use. I may come back to try and finish this off. It was more of a personal challenge to be honest. I thought it would be fun but instead I ended up with a migraine. Maybe I’m getting too old for writing code… I don’t know. I do love it, but I get frustrated when I can’t solve a problem I believe should be simple.

Just out of curiosity, how long did it take you to come up with your solution from idea to code? I guess it goes to show what happens when you get your mind set on doing things a certain way. It blinds you to all the other options.

I’m also extremely impressed with how easily you understood the problem, despite my awful explanation. Haha.

Many thanks again. You’re a star!

#7

It took about twenty minutes. You did most of the work by mentioning recursion; that immediately suggests an approach of doing the same thing several times to an evolving set of inputs. Then it’s just breaking it down.

I’ve had a fair amount of practice with an annual coding challenge I like to play with: Https://www.adbentofcode.com. It’s lots of algorithm style problems like this.

As to your explanation, it wasn’t awful at all! You gave your inputs, your outputs, and some code which did parts of the work. Questions like yours are easy to work with.

#9

I just wanted to say thanks again. I’ve been having a go on adventofcode.com (still on the challenges from 2015) and I’m really enjoying it. To be fair, I thought it would be easy, and whilst some of them have been, some of them have actually been quite challenging. Thanks for mentioning the site.

1 Like
Sponsor our Newsletter | Privacy Policy | Terms of Service