[구현]itertools 라이브러리 직접 구현 및 활용 정리

python에서 제공하는 itertools 라이브러리 중 조합에 관련한 4개!

combinations(조합) , permutations(순열) , product(중복순열), combinations_with_replacement

요 4개를 직접 구현해보았다.

간단하게 재귀로.. DFS로도 구현이 된다하던데.. (이건.. 나중에.. 또 미룬다.. ㅋㅋ)

재귀로는 요런 식이다.

ex > 

combinations(['a','b','c'],2)=[['a']+combinations(['b','c'],1)]+ [['b']+combinations(['a','c'],1)]+[['c']+combinations(['a','b'],1)]

 

아주 간단쓰하므로 빠르게 코드로 슉슉

---

combinations(조합)

서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 상관 없음)

조합공식

from itertools import permutations,combinations,product

list(combinations([1,2,3,4],3))
#[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

def comb_li(l,n):
    result=[]
    if n==1:
        for i in l:
            result.append([i])
    else:
        for idx,i in enumerate(l):
            sl=l[idx+1:]
            for j in comb_li(sl,n-1):
                result.append([i]+j)
    return result
comb_li([1,2,3,4],3)
#[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

핵심은 13번째 라인에 sl

조합은 순서 바뀜에 상관이 없기때문에, 이미 경우의 수에 활용된 원소는 계속 제거해야한다.

---

permutations(순열)

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

순열 공식

from itertools import permutations,combinations,product

list(permutations([1,2,3],2))
#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

def perm_li(l,n):
    result=[]
    if n==1:
        for i in l:
            result.append([i])
    else:
        for idx,i in enumerate(l):
            sl=l[:idx]+l[idx+1:]
            for j in comb_li(sl,n-1):
                result.append([i]+j)
    return result

perm_li([1,2,3],2)
#[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

이 친구는 이미 조합에 사용했다고해도, 순서가 달라지면서 또 이용해야한다.

---

product(중복순열)

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

 

중복순열

from itertools import permutations,combinations,product

list(product([1,2,3],repeat=2))
#[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

def pro_li(l,n):
    result=[]
    if n==1:
        for i in l:
            result.append([i])
    else:
        for idx,i in enumerate(l):
            sl=l
            for j in comb_li(sl,n-1):
                result.append([i]+j)
    return result
pro_li([1,2,3],2)
#[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

이친구는 중복도 상관없고, 순서도 상관없으니 그냥 계속 똑같은 l 에서 뽑고 또 뽑고..

 

**이 친구가 생각보다 필요할때가 있었다.

단순히 배열에 대한 중복 순열로도 가치가 있지만,

for i in product([1,2,3], [4,5], ['a']) :
    print(i,end=" ")
#(1, 4, 'a') (1, 5, 'a') (2, 4, 'a') (2, 5, 'a') (3, 4, 'a') (3, 5, 'a') 

요렇게 여러 배열을 조합하는 방법으로도 많이 썼던것 같다.

(repeat argument도 product([1,2,3],[1,2,3])을 간단하게 표현한것일뿐)

---

combinations_with_replacement (중복조합)

중복 가능한 n개중에서 r개를 선택하는 경우의 수(순서 상관 없음)

중복 조합

 

from itertools import permutations,combinations,product,combinations_with_replacement

list(combinations_with_replacement([1,2,3],2))
#[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

def cwithr_li(l,n):
    result=[]
    if n==1:
        for i in l:
            result.append([i])
    else:
        for idx,i in enumerate(l):
            sl=l[idx:]
            for j in comb_li(sl,n-1):
                result.append([i]+j)
    return result

cwithr_li([1,2,3],2)
#[[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

combination 에서 자기자신까지 넣어서~