순열

구현

반복문 방식

# {1, 2, 3}의 모든 순열을 구하기 위한 3중 for문

for i in range(1, 4):
    for j in range(1, 4):
        # i와 j가 겹치지 않는 경우에만 다음 단계로
        if i != j:
            for k in range(1, 4):
                # i, j, k가 모두 겹치지 않는 경우 출력
                if i != k and j != k:
                    print(i, j, k)

해설
- i, j, k는 모두 달라야 하므로 if j != i, if k != i and k != j를 검사
한계점
- 이 방식은 원소의 개수가 3개로 고정되어 있을 때는 유효하지만, 원소가 4개가 되면 for문을 4번, n개가 되면 n번 중첩해야 함
- 이처럼 원소의 개수가 유동적일 때는 사용할 수 없다는 명확한 한계가 존재
  
  ⇒ 이러한 한계를 보완한 것이 재귀 방식

재귀 방식

def perm(selected, remaining):
    """
    Args:
        selected (list): 현재까지 선택된 원소들의 순열 (선택된)
        remaining (list): 아직 선택되지 않은 원소들 (선택할)
    """
    # 기저 조건(Base Case): 더 이상 선택할 원소가 없으면 순열 하나가 완성된 것
    if not remaining:
        print(selected)
        return

    # 재귀 호출(Recursive Step)
    # 남아있는 원소들(remaining)을 하나씩 순회하며 다음 자리에 놓을 원소를 선택
    for i in range(len(remaining)):
        # i번째 원소를 이번 순열에 추가
        pick = remaining[i]

        # i번째 원소를 제외한 새로운 '남은 원소' 리스트 생성
        new_remaining = remaining[:i] + remaining[i + 1 :]

        # 새로운 '선택된 원소'와 '남은 원소'로 자기 자신을 다시 호출
        perm(selected + [pick], new_remaining)

# --- 실행 코드 ---
# 처음에는 아무것도 선택되지 않았고([]), 모든 원소가 남아있음([1, 2, 3])
perm([], [1, 2, 3])

조합

구현

반복문 방식

numbers = [1, 2, 3, 4]
n = len(numbers)

# 3개의 원소를 뽑으므로 3중 for문 사용
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            print(numbers[i], numbers[j], numbers[k])

해설
- $i<j<k$ 구조를 이용
- 1<2<3, 1<2<4, 1<3<4, 2<3<4
- 다음 반복문의 시작 범위를 이전 반복문보다 1 크게 설정
- range(i + 1, ...) 덕분에 i번째에서 선택된 숫자보다 작은 숫자는 j번째에서 아예 고려되지 않음. 이 간단한 규칙만으로 순서가 다른 중복 조합을 자연스럽게 제거할 수 있음

재귀 함수 (Backtracking) 방식

<aside> 📌

결정의 연속 ⇒ "현재 요소를 포함시킬지" 결정하고, "나머지 요소들로 나머지 개수를 채우는" 재귀적 구조

</aside>

첫 번째 원소(1)를 결정했다고 가정
이제 나머지 원소({2, 3, 4}) 중에서 **나머지 개수(2개)**를 뽑는 모든 조합을 구하라고 재귀 호출
위 과정이 끝나면, 다시 돌아와 첫 번째 원소를 결정하지 않았다고 가정하고, 나머지 원소({2, 3, 4}) 중에서 **뽑아야 할 개수(3개)**를 모두 뽑으라고 재귀 호출

def comb(arr, r):
    """
    Args:
        arr (list): 원본 배열
        r (int): 뽑을 개수

    Returns:
        list: 모든 조합이 담긴 2차원 리스트
    """
    result = []

    # 기저 조건(Base Case): 뽑을 개수가 0이면, 빈 리스트를 담은 리스트를 반환하여 조합 완성
    if r == 0:
        return [[]]

    # 재귀 호출(Recursive Step)
    for i in range(len(arr)):
        # i번째 원소를 첫 번째 요소로 선택
        elem = arr[i]

        # i번째 원소 이후의 나머지 리스트에서
        # 나머지 (r-1)개의 조합을 재귀적으로 구함
        for rest in comb(arr[i + 1 :], r - 1):
            # 선택한 요소(elem)와 나머지 조합(rest)을 합쳐 결과에 추가
            result.append([elem] + rest)

    return result

# --- 실행 코드 ---
all_combs = comb([1, 2, 3, 4], 3)
print(all_combs)