python 순열, 조합

코딩테스트 준비를 하다보면 combination, permutation을 활용하는 dfs 기반 문제들이 많습니다. python의 itertools 라이브러리를 사용하는 방법도 있겠지만, 테스트 환경에 따라서 사용이 불가한 경우도 있는 것 같아서, 저의 경우 이 두 함수는 외워두는 편입니다.

Permutation (순열)

서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서O, 중복X)

def permutation(arr,r):
    result = []

    def permute(p,index):
        if len(p)==r:
            result.append(p)
            return
        
        for idx, data in enumerate(arr):
            if idx not in index:
                permute(p+[data],index+[idx])
    
    permute([],[])

    return result

lst = list(range(5))
result = permutation(lst,3)
for r in result:
    print(r)

Combination (조합)

서로 다른 n개 중에 r개를 선택하는 경우의 수(순서X, 중복X)

def combination(arr,r):
    result = []

    def combinate(c,index):
        if len(c)==r:
            result.append(c)
            return
        
        for idx,data in enumerate(arr):
            if idx>index:
                combinate(c+[data],idx)
        
    combinate([],-1)
    
    return result

lst = list(range(5))

for r in combination(lst,3):
    print(r)

Pi(중복순열)

중복 가능한 n개 중에서 r개를 선택하는 경우의 수(순서O, 중복O)

def pi(arr,r):
    result = []

    def _pi(p,index):
        if len(p)==r:
            result.append(p)
            return
        
        for idx,data in enumerate(arr):
            _pi(p+[data],index+[idx]) # permutate 함수와 달리 if문이 없다.
        
    _pi([],[])
    return result

lst = list(range(4))
cases = pi(lst,2)

print(cases)
print(len(cases))

Harmonic(중복조합)

중복 가능한 n개 중에서 r개를 선택하는 경우의 수(순서X, 중복O)

def harmonic(arr,r):
    result = []

    def _harmonic(h,index):
        if len(h)==r:
            result.append(h)
            return
        
        for idx,data in enumerate(arr):
            if idx>=index: # combinate 함수와 달리 등호도 포함
                _harmonic(h+[data],idx)
        
    _harmonic([],-1)
    return result

lst = list(range(4))
cases = harmonic(lst,2)

print(cases)
print(len(cases))