Исключить определенные перестановки строки

Question

Исключить определенные перестановки строки

Как исключить определенные перестановки? Например, если я установлю для $ str значение «heyy» и хочу, чтобы он исключил все перестановки, в которых есть «yy» (два y вместе), как я могу это сделать?

Таким образом, это напечатало бы, например, «хей», но не «хай».

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.

Заранее спасибо!

0

algorithm permutation php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это то, что вы ищете?

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.
}
}
}

Если это усложняется, вы также можете написать для него отдельную функцию (этот пример — перебирать список запрещенных подстрок):

$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.
}
}
}

1