재귀 알고리즘을 사용하여 집합의 모든 하위 집합을 생성하려면 어떻게 해야 합니까?

재귀 알고리즘을 사용하여 집합의 모든 부분 집합 찾기

n개 요소로 구성된 집합이 주어지면 가능한 모든 부분 집합을 찾는 것이 일반적인 작업입니다. 이 글에서는 이를 달성하기 위한 효율적인 재귀 알고리즘에 대한 단계별 설명을 제시합니다.

재귀적 접근 방식

알고리즘은 각 요소에 대해 다음과 같은 아이디어를 기반으로 합니다. 세트에는 두 가지 가능성이 있습니다:

1. 다음 요소 포함: 그러면 요소를 포함하는 새 하위 집합이 생성됩니다.
2. 요소 제외: 요소를 제외하는 새 하위 집합이 생성됩니다.

두 가지 가능성을 모두 고려하여 각 요소마다 가능한 모든 조합을 다루므로 모든 하위 집합을 찾습니다.

단계별 설명

집합 {1, 2, 3, 4, 5}를 예로 들어보겠습니다.

1. 기본 사례: n=의 경우 1의 경우 세트에는 단일 요소(예: {1})가 있습니다. 하위 집합은 {{}}(빈 집합) 및 {{1}}(1개만 포함)입니다.

2. 재귀 사례: n>1의 경우 다음을 깰 수 있습니다. 문제를 두 개의 하위 문제로 나눕니다.

   • {1, 2, 3, 4, 5-1}: 첫 번째 n-1 요소에 대한 알고리즘을 재귀적으로 호출하고 하위 집합 집합을 얻습니다.
   • 하위 집합 집합의 복사본을 두 개 만듭니다. 한 사본은 모든 하위 집합에 요소 n을 포함하기 위한 것이고, 다른 사본은 이를 제외하기 위한 것입니다.
   • 추가 n을 포함 복사본의 하위 집합에 추가: 예를 들어, {{}, {1}, {2}}가 있는 경우 5를 추가하면 {{}, {1}, {2}, {5}가 됩니다. , {1, 5}, {2, 5}}.
   • 두 복사본의 합집합을 취합니다. 이는 우리에게 완전한 세트를 제공합니다. 하위 집합.

예

{1, 2, 3, 4, 5}의 하위 집합을 재귀적으로 계산해 보겠습니다.

• 1단계 (n=1): 하위 집합 = {{}, {1}}
• 2단계(n=2): 하위 집합 = {{}, {1}, { 2}, {1, 2}} ({2}에 대한 사본 만들기)
• 3단계 (n=3): 하위 집합 = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}} ({2} 복사본에 3 추가)
• 4단계(n=4): 하위 집합 = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2 , 4}, {1, 2, 4}} ({3} 복사본에 4 추가)
• 5단계(n=5): 하위 집합 = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}} ({4}에 5 추가 복사)

따라서 전체 하위 집합은 {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}}.

위 내용은 재귀 알고리즘을 사용하여 집합의 모든 하위 집합을 생성하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!