[Python] itertools 없이 순열, 조합 구현하기

알고리즘 문제를 풀다보면 가끔 순열, 조합을 구현해야한다..

코테에서도 가끔 등장하는데 문제 볼때마다 까먹어서 다시 공부를 해야한다,,

내가 보고 공부하려고 기록하는 파이썬으로 순열과 조합 구현하는 코드!

itertools를 사용하지 못할 수도 있어 직접 구현하는 방식만 공부했다

 

순열(n개 중에 r개를 선택해서 만들수 있는 모든 경우의 수)

조합(n개 중에 순서 상관없이 r개를 뽑는 모든 경우의 수)

1. 재귀함수를 이용한 조합

def comb(arr, n):
    result = []
    if n > len(arr):
        return result

    if n == 1:
        for i in arr:
            result.append([i])
            
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in comb(arr[i + 1:], n - 1):
                result.append([arr[i]] + j)

    return result
    
    
arr = [1, 2, 3]
print(comb(arr, 1))  # [[1], [2], [3]]
print(comb(arr, 2))  # [[1, 2], [1, 3], [2, 3]]
print(comb(arr, 3))  # [[1, 2, 3]]

 

2. 재귀함수를 이용한 순열

def perm(arr, n):
    result = []
    if n > len(arr):
        return result

    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr)):
            ans = [i for i in arr]
            ans.remove(arr[i])
            for p in perm(ans, n-1):
                result.append([arr[i]]+p)

    return result
    
    
arr = [1, 2, 3]
print(perm(arr, 3))  # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

arr = [1, 2, 3]
N = 3

sel = [0] * N  # 결과들이 저장될 리스트
check = [0] * N  # 해당 원소를 이미 사용했는지 안했는지 체크


def perm(idx):
    # 다 뽑아서 정리했다면
    if idx == N:
        print(sel)
    else:
        for i in range(N):
            if check[i] == 0:
                sel[idx] = arr[i]  # 값을 써라
                check[i] = 1  # 사용했다는 표시
                perm(idx+1)
                check[i] = 0  # 다음 반복문을 위한 원상복구

perm(0)

그 외 방법)

arr = [1, 2, 3]
N = 3

def perm(idx):
    if idx == N:
        print(arr)

    else:
        for i in range(idx, N):
            # 순서를 바꾸고
            arr[idx], arr[i] = arr[i], arr[idx]
            perm(idx + 1)
            # 원상복구
            arr[idx], arr[i] = arr[i], arr[idx]

perm(0)

arr = [1, 2, 3]
N = 3
sel = [0] * N  # 뽑은 결과

def perm(idx, check):
    if idx == N:
        print(sel)
        return

    for j in range(N):
        # j번째 원소 활용했으면 사용하면 안됨
        if check & (1 << j):
            continue

        sel[idx] = arr[j]
        perm(idx+1, check | (1 << j))  #원상복구 필요없음


perm(0, 0)

# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

 

3. 기본 내장함수로 간단하게 구하기

3-1. 순열

import itertools

data = [1, 2]

for i in itertools.permutations(data, 2):
    print(list(i), end= ' ')

# 예시
nums = ["1","7"]
    num = []
    for i in range(len(nums)):
        for j in itertools.permutations(nums, i+1):
            num.append(int(''.join(j)))
    num_list = list(set(num))
    
출력 결과 : [1,71,17,7]

 

3-2. 조합

import itertools

data = [1, 2, 3]

for i in itertools.combination(data, 3):
    print(list(i), end=' ')