문자열의 특정 순열을 제외하십시오

코드 원래 this thread에서 코드를 제외하십시오.문자열의 특정 순열을 제외하십시오

특정 순열을 어떻게 제외합니까? 예를 들어 $ str을 "heyy"로 설정하고 "yy"(두 개의 y가 함께 있음)가있는 모든 순열을 제외 시키려면 어떻게해야합니까?

그래서 "hyye"는 인쇄하지만 "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.

미리 감사드립니다.

출처

2015-01-06 indiqa

은 구현 방식에 따라 크게 것이 더 복잡하게되면

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

, 당신은 또한 (이 예는 금지 문자열 목록을 반복하는 것입니다) 그것을위한 별도의 기능을 쓸 수있다 당신은 제외를 정의합니다. 금지 된 문자열, 정규 표현식 또는 더 복잡한 규칙 목록일까요? 그런 다음 순열이 계산되거나 생성 된 후에 제외를 적용 할 수 있습니다. – ptrk

최적의 방법은 무엇입니까? 나는 어딘가에 if 문을 쓰고 문자 조합의 목록을 건너 뛰기 만하면 될지 모르지만 그렇게하는 법이나 가능하다면 생각하고있다. – indiqa

이게 당신이 찾고 있는게 있니?

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

출처

2015-01-06 23:00:05 Keelan

정확히 내가 뭘 찾고 있어요! :) 정말 고맙습니다! – indiqa

문자열의 특정 순열을 제외하십시오

답변

관련 문제