CODEWITHSUNDEEP
phpalgorithmpermutation
joakim.g
joakim.g

Reputation: 71

Exclude certain permutations of a string

Code originally from this thread.

How do I exclude certain permutations? For example if I set $str to "heyy" and want it to exclude all permutations which has "yy" (the two y's together) in it, how could I do that?

So it would print for example "hyey", but not "hyye".

mb_internal_encoding('UTF-8');

// function to generate and print all N! permutations of $str. (N = strlen($str)).
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 swap(&$str,$i,$j) {
    $chars = array();
    for ($p = 0; $p < mb_strlen($str); $p++) {
        $chars[] = mb_substr($str, $p, 1);
    }
    $temp = $chars[$i];
    $chars[$i] = $chars[$j];
    $chars[$j] = $temp;
    $str = implode($chars);
}

$str = "heyy";

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

Thanks in advance!

Upvotes: 0

Views: 117

Answers (1)

user1544337
user1544337

Reputation:

Is this what you're looking for?

function permute($str,$i,$n)
{
    if ($i == $n && strpos($str, 'yy') === false)    // note the extra condition
    {
        print "$str\n";
    }
    else
    {
        for ($j = $i; $j < $n; $j++)
        {
            swap($str,$i,$j);
            permute($str, $i+1, $n);
            swap($str,$i,$j); // backtrack.
        }
    }
}

If this becomes more complicated, you could also write a separate function for it (this example is to iterate over a list of forbidden substrings):

$skip = array('yy', 'xx');

function valid_permutation($str)
{
    global $skip;
    // check all forbidden substrings
    foreach ($skip as $substring)
        if (strpos($str, $substring) !== false)
            return false;
    // no substring matches
    return true;
}

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

Upvotes: 1

Related Questions