재귀적 접근 방식을 사용하여 주어진 문자 집합에서 특정 크기의 가능한 모든 조합을 생성하려면 어떻게 해야 합니까?

단일 집합에서 조합을 생성하는 알고리즘

당면 과제는 지정된 집합의 가능한 모든 조합을 생성할 수 있는 알고리즘을 고안하는 것입니다. 주어진 문자 세트에서 크기를 추출하여 샘플링 알고리즘으로 효과적으로 작동합니다. 순열 알고리즘과 달리 이 기술은 조합 내에서 문자의 반복을 허용합니다.

재귀적 접근 방식

이 문제를 해결하기 위해 우리는 다음을 입력으로 사용하는 재귀 함수를 사용합니다. 문자 집합, 원하는 조합 크기, 중간 조합 배열(초기 반복을 위해 원래 집합으로 초기화됨).

1. 기본 사례: 크기가 1인 경우, 이 함수는 현재 조합 세트를 반환합니다.

2. 재귀 단계:

   • 새 조합 세트에 대해 빈 배열을 만듭니다.
   • 세트의 각 기존 조합과 문자를 연결하여 새 배열에 추가합니다.
   • 업데이트된 문자 세트(변경되지 않음), 축소된 크기 및 새로운 조합 세트를 사용하여 동일한 함수를 호출합니다.

구현 예

다음 PHP 코드는 재귀 알고리즘의 구현을 보여줍니다.

function sampling($chars, $size, $combinations = array()) {

    // Base case
    if (empty($combinations)) {
        $combinations = $chars;
    }

    // Size 1 case
    if ($size == 1) {
        return $combinations;
    }

    // Initialize new combinations array
    $new_combinations = array();

    // Generate new combinations by concatenating existing and new characters
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    // Recursive call
    return sampling($chars, $size - 1, $new_combinations);

}

사용 예

기능을 보여주기 위해 문자 집합을 고려해 보겠습니다.

$chars = array('a', 'b', 'c');

알고리즘을 사용하면 크기 2의 모든 조합을 생성할 수 있습니다. :

$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 중국어 웹사이트의 기타 관련 기사를 참조하세요!