재귀 알고리즘을 사용하여 PHP에서 주어진 세트의 모든 조합을 어떻게 생성할 수 있습니까?

PHP의 알고리즘을 사용하여 모든 조합 생성

컴퓨터 과학의 기본 작업 중 하나는 주어진 집합에서 조합을 생성하는 것입니다. 이 맥락에서 조합은 지정된 크기를 가진 원래 집합의 요소 하위 집합을 나타냅니다.

예를 들어 집합 A = {A, B, C}를 생각해 보세요. 다양한 크기의 조합을 얻을 수 있는 방법은 다음과 같습니다.

재귀 알고리즘을 사용하여 조합 생성

이 문제를 해결하기 위해 가능한 모든 조합을 탐색하는 재귀 알고리즘을 사용할 수 있습니다. . 단계별 분석은 다음과 같습니다.

1. 빈 배열 $combinations를 초기화하여 조합을 저장합니다.
2. $size가 1과 같으면 기본 사례에 도달한 것입니다. $combinations를 반환할 수 있습니다.
3. $chars와 현재 항목을 반복합니다. $combinations.
4. 각 조합과 문자에 대해 문자를 조합에 추가하고 새 조합을 $new_combinations에 추가합니다.
5. 업데이트된 $new_combinations로 샘플링 함수를 재귀적으로 호출하고 $size를 다음과 같이 줄입니다. 1.

구현 PHP

function sampling($chars, $size, $combinations = []) {
    if (empty($combinations)) {
        $combinations = $chars;
    }
    if ($size == 1) {
        return $combinations;
    }
    $new_combinations = [];
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }
    return sampling($chars, $size - 1, $new_combinations);
}

예제

원래 집합 A = {A, B, C}.

$chars = ['A', 'B', 'C'];
$output = sampling($chars, 2);
var_dump($output);

출력

array(9) {
  [0]=>
  string(2) "AA"
  [1]=>
  string(2) "AB"
  [2]=>
  string(2) "AC"
  [3]=>
  string(2) "BA"
  [4]=>
  string(2) "BB"
  [5]=>
  string(2) "BC"
  [6]=>
  string(2) "CA"
  [7]=>
  string(2) "CB"
  [8]=>
  string(2) "CC"
}

이 알고리즘은 주어진 세트에서 특정 크기의 모든 조합을 생성하기 위한 체계적인 접근 방식을 제공합니다. 재귀적 특성을 통해 입력 세트의 크기에 관계없이 가능한 모든 조합을 효율적으로 탐색할 수 있습니다.

위 내용은 재귀 알고리즘을 사용하여 PHP에서 주어진 세트의 모든 조합을 어떻게 생성할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!