순열, 조합 파이썬 알고리즘 총정리

출처

파이썬의 yield 키워드와 제너레이터(generator) | Engineering Blog by Dale Seo

 

원래도 간단하게 알고있었고 다른사람의 코드를 보고 이해하고넘어갔는데

아무래도 자주쓰이고 하니 다시한번 복습한다는 마인드로 공부하였다

 

조합

def combinations_2(array, r):
    for i in range(len(array)):
        if r == 1: # 종료 조건
            yield [array[i]]
        else:
            for next in combinations_2(array[i+1:], r-1):
                yield [array[i]] + next

from itertools import combinations

print('itertools 모듈을 사용한 조합구현')
for i in combinations([1,2,3,4],3): # 똑같이 제너레이터로 저장되어있음
    print(i, end=' ')



print("\n\n조합 직접 구현")
for i in combinations_2([1,2,3,4], 3):
    print(i, end=" ")

중복조합

def combinations_3(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            ## array[i+1: ] -> array[i: ] 변경
            for next in combinations_3(array[i:], r-1):
                yield [array[i]] + next

from itertools import combinations_with_replacement

print('itertools 모듈을 사용한 중복 조합구현')
for cwr in combinations_with_replacement([1,2,3,4], 3):
    print(cwr, end=" ")

print("\n\n중복조합 직접 구현")
for i in combinations_3([1,2,3,4], 3 ):
    print(i, end=" ")

모듈을 사용한방식이 직접구현보다 훨씬 빠르다 

그리고 백준에서도 사용가능한것같으니 시간초과를 막기위해 써주는게 좋을것같다

다만 나는 작동방식을 완벽하게 내것으로 만들고싶었다

yield 라는것은 이번에 처음 알게되었는데 꽤 쓸만한것같다

출력용 리스트를 만들지않아도된다는게 맘에 들었다 뿐만아니라 메모리도 절약해준다고한다

 

순열

def permutations_2(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in permutations_2(array[:i]+array[i+1:], r-1):
                yield [array[i]] + next

from itertools import permutations

print('itertools 모듈을 사용한 순열 구현')
for i in permutations([1,2,3,4], 2):
    print(i, end=" ")

print("\n\n순열 직접 구현")
for i in permutations_2([1,2,3,4],2):
    print(i, end=" ")

중복순열

def permutations_2(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in permutations_2(array[:i+1]+array[i+1:], r-1):
                yield [array[i]] + next

from itertools import product

print('itertools 모듈을 사용한 중복순열 구현')
for i in product(range(1,5), range(1,5)):
    print(i, end=" ")

print("\n\n중복 순열 직접 구현")
for i in permutations_2([1,2,3,4],2):
    print(i, end=" ")

중복순열은 중복 조합과 다르게 product라고 불리는 다른시스템을 사용한다

예를들어 셔츠4벌바지5벌신발2켤레가있을때 가능한 모든 순열을 출력할수있다

 

내가 이걸 다시 찾아보게된건

그러니까 같은 수가 들어갔을때 순열

[1, 1, 2, 2]중로 만들수있는 수열을 구하는법을 알아보기위해서였는데

 

아쉽게도 이것을 해결해주는 모듈이나 재귀함수는 아직 발견하지못하였다