PHP 전체 순열 재귀 알고리즘 샘플 코드-PHP 튜토리얼-php.cn

PHP 전체 순열 재귀 알고리즘 샘플 코드

怪我咯

풀어 주다： 2023-03-13 17:56:01

원래의

1785명이 탐색했습니다.

재귀는 중요한 프로그래밍 기술입니다. 이 메서드는 함수가 내부에서 자체적으로 호출되도록 하는 데 사용됩니다. 한 가지 예는 계승 계산입니다. 0의 계승은 구체적으로 1로 정의됩니다. 더 큰 숫자의 계승은 1 * 2 * ...를 계산하여 구하며, 계승을 계산할 숫자에 도달할 때까지 매번 1씩 증가합니다.

알고리즘 원리
P가 n 원소의 완전한 배열을 나타내고, Pi가 i 원소를 포함하지 않는 n 원소의 완전한 배열을 나타낸다면, (i) Pi는 배열 Pi 앞에 접두사 i가 붙은 배열을 나타냅니다. , 그러면 n 요소의 전체 배열은 다음과 같이 재귀적으로 정의될 수 있습니다.
① n=1이면 배열 P에는 하나의 요소 i만 있습니다.
② n>1이면 전체 배열 P는 배열(i)로 구성됩니다. Pi
정의에 따르면, (k-1) 요소의 순열 Pi가 생성된 경우 각 Pi 앞에 요소 i를 추가하면 k 요소의 순열이 생성될 수 있음을 알 수 있습니다.
코드 구현

코드는 다음과 같습니다.

function rank($base, $temp=null)
{
    $len = strlen($base);
    if($len <= 1)
    {
        echo $temp.$base.&#39;<br/>&#39;;
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
}
rank(&#39;123&#39;);

로그인 후 복사

그러나 여러번의 테스트를 거쳐 문제가 발견되었습니다. 동일한 요소가 있으면 전체 배열이 반복됩니다.
예를 들어 '122'의 전체 배열에는 '122', '212', '221' 세 가지 상황만 있지만 위의 방법이 반복됩니다.
약간 수정, 중복 식별을 위한 플래그 추가, 문제 해결(코드는 다음과 같습니다):

코드는 다음과 같습니다:

function fsRank($base, $temp=null)
{
    static $ret = array();
    $len = strlen($base);
    if($len <= 1)
    {
        //echo $temp.$base.&#39;<br/>&#39;;
        $ret[] = $temp.$base;
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            $had_flag = false;
            for($j=0; $j<$i; ++$j)
            {
                if($base[$i] == $base[$j])
                {
                    $had_flag = true;
                    break;
                }
            }
            if($had_flag)
            {
                continue;
            }
            fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
    return $ret;
}
print &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r(fsRank(&#39;122&#39;));
print &#39;

로그인 후 복사

위 내용은 PHP 전체 순열 재귀 알고리즘 샘플 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!