Get all possible combination (preffix/suffix) of string

Question

I am trying to write a function that will take lets say "hey there" then create an array of all prefix of this string. So it would return "h", "he", "hey", "hey ", "hey t" etc etc.

Then I would like the same function to create a second array of all suffixs (counting backwards down the string). so for the same string it would return "e", "er", "ere", "ereh", "ereht", "ereht " etc

I am sturggling a bit to figure this one out but I have managed to get the following which gets all possible combinations of a string I just need to get it to do it only in order.

$str    = "hey there";

function permute($str,$i,$n) {
   if ($i == $n)
       print "$str\n";
   else {
        for ($j = $i; $j < $n; $j++) {
          swap($str,$i,$j);
          permute($str, $i+1, $n);
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   

permute($str,0,strlen($str)); // call the function.

}

Any help greatly appreciated.

A combination of substr, strrev and loops would do the trick. — Virus721, Oct 02 '13 at 11:56
Not a duplicate, I don't want to generate all combinations like stated in the post. Please read it before commenting, and I see I will check these functions out thankyou. — Simon Staton, Oct 02 '13 at 11:57
Hardly worth answering: `function permute($string) { $length = strlen($string); $result = array(); for ($i = 1; $i <= $length; $i++) { $result[] = substr($string,0,$i); } return $result; } function permuteboth($string) { $results = array(); $results[] = permute($string); $results[] = permute(strrev($string)); return $results; } $str = "hey there"; $results = permuteboth($str); var_dump($results); ` — Mark Baker, Oct 02 '13 at 11:57
More fun would be using Tries to do it, at least it's learning something useful about data structures as well — Mark Baker, Oct 02 '13 at 11:59

score 2 · Accepted Answer · answered Oct 02 '13 at 11:58

Is this what you're trying to do?

<?php
    function getPrefixSuffix($string, &$prefixes = array(), &$suffixes = array()) {
        $stringLength = strlen($string);
        for ($i = 1; $i < $stringLength; $i++) {
            $prefixes[] = substr($string, 0, $i);
        }
        for ($i = $stringLength - 1; $i >= 1; $i--) {
            $suffixes[] = strrev(substr($string, $i));
        }
    }

    getPrefixSuffix("hey there", $prefixes, $suffixes);

    print_r($prefixes);
    /*
        Array
        (
            [0] => h
            [1] => he
            [2] => hey
            [3] => hey 
            [4] => hey t
            [5] => hey th
            [6] => hey the
            [7] => hey ther
        )
    */

    print_r($suffixes);
    /*
        Array
        (
            [0] => e
            [1] => er
            [2] => ere
            [3] => ereh
            [4] => ereht
            [5] => ereht 
            [6] => ereht y
            [7] => ereht ye
        )
    */
?>

DEMO

bizzehdee · Answer 2 · 2013-10-02T13:45:53.947

0

would a simple for loop and a couple of substr's do the same?

$prefixes = array();
$suffixes = array();
$str = "hey there";
$l = strlen($str);
for($i=1; $i<$l; $i++) {
  $prefixes[] = substr($str, 0, $i);
  $suffixes[] = strrev(substr($str, $l-$i, $i));
}

demo

edited Oct 02 '13 at 13:45

answered Oct 02 '13 at 11:58

bizzehdee

20,289
11
46
76

Add `strrev` to `$suffixes` as OP wants it as `ereht` instead of `there`. – h2ooooooo Oct 02 '13 at 12:00

score 0 · Answer 3 · answered Oct 02 '13 at 12:21

This should work. I wrote 3 functions. The first one simply gets all the prefixes by printing at every append. The third one is the swap method you wrote. The second one simply swaps backwards the string, and then it calls getPrefix. Please note that the original string is left untouched.

$str = "hey there"

function getPrefix($str)
{
    $printString = "";
    for ($i = 0; $i < strlen($str); $i++)
    {
        $printString .= $str[$i];
        print ($printString);
    }
}

function getBackwards($str)
{
    if (strlen($str) % 2 == 0)
    {
        for ($i = 0; $i < strlen($str)/2; $i++)
            swap ($str, $i, strlen($str)-1-$i);
    }
    else
    {
        for ($i = 0; $i < (strlen($str)-1)/2; $i++)
            swap ($str, $i, strlen($str)-1-$i);
    }
    getPrefix($str);
}

function swap(&$str,$i,$j)
{
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}

Get all possible combination (preffix/suffix) of string

3 Answers3