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

Question

Код оригинал от this thread.

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

Таким образом, печатается, например, «hyey», но не «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. 

Заранее благодарен!

Answer 1

Вы хотите что-то ищите?

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