[Python] 순열조합 itertools 없이 직접 구현하기 (순열 조합 중복순열 중복조합 )

 

 

 

n개 중 m개를 뽑고자 할 때 

1. 중복 여부

2. 순서

를 고려해야한다.

 

 

순열: 순서 상관 있음

조합: 순서 상관 없음

그리고 중복순열과 중복조합

 

 

이 글에서는 itertools 없이 직접 짠 코드를 첨부하였다

itertools 사용하는 방식은 해당 글 참고!

https://cryosleep.tistory.com/4

순열, 조합 (Python3)

 

 

 

 

 

 

조합 Combination

def pick(n, bucket, k):

    if k == 0:
        print(*bucket)
        return

    lastIndex = len(bucket) - k - 1


    if len(bucket) == k:
        smallest = 0
    else:
        smallest = bucket[lastIndex] + 1

    for i in range(smallest, n):
        bucket[lastIndex + 1] = i
        pick(n, bucket, k-1)

 

실행 예시: 

5개 중 3개 뽑는 경우

 

 

 

 

 

중복조합 Combination with repetition

def pick(n, bucket, k):


    if k == 0:
        print(*bucket)
        return

    lastIndex = len(bucket) - k - 1


    if len(bucket) == k:
        smallest = 0
    else:
        smallest = bucket[lastIndex]	#이 부분만 차이가 있음!

    for i in range(smallest, n):
        bucket[lastIndex + 1] = i
        pick(n, bucket, k-1)

조합에서는 마지막에 뽑은 것보다 큰 것을 뽑았지만

중복조합에서는 크거나 같은 것을 뽑음

 

조합 예시와 마찬가지로 5개중 3개를 뽑을 경우의 실행 결과

 

 

 

 

 

 

 

중복순열 Permutation with Repetition

 

bucket에 새로운걸 뽑을때 매번 전체 아이템 중에서 뽑음

def pick(n, bucket, k):

    if k == 0:
        print(*bucket)
        return

    lastIndex = len(bucket) - k - 1

    # if len(bucket) == k:
    #     smallest = 0
    # else:
    #     smallest = bucket[lastIndex] 

    smallest = 0    #이부분만 차이가 있음

    for i in range(smallest, n):
        bucket[lastIndex + 1] = i
        pick(n, bucket, k-1)

5개중 3개 뽑을 경우

 

 

순열 Permutation

def pick(n, bucket, k):

    if k == 0:
        print(*bucket)
        return

    lastIndex = len(bucket) - k - 1
    smallest = 0

    for i in range(smallest, n):
        j = 0
        flag = 0
        for j in range(0, lastIndex+1):
            if bucket[j] == i:
                flag = 1
        if flag == 1:
            continue

        bucket[lastIndex + 1] = i
        pick(n, bucket, k-1)

실행결과

 

 

해당 코드를 조금 수정해서 입력해주면 백준 15649 N과 M(1)을 해결할 수 있다 

(n, k입력받기, 1부터 n까지로 범위 변경해주기) 

 

코딩테스트를 파이썬으로 공부하는 중이라

C언어로 진행된 수업의 코드를 파이썬으로 그대로 옮겨본 건데

다시 보니 지저분해서 수정을 더 해볼 예정... 

 

 

+)

다음 순서의 순열을 구하는 글을 새롭게 작성했습니다!

 

[🖥] - [python3] itertools 없이 다음 순열 구하기 (C++ next_permutation 파이썬으로 구현)

[python3] itertools 없이 다음 순열 구하기 (C++ next_permutation 파이썬으로 구현)