파이썬으로 순열과 조합 구현하기 (+중복순열, 중복조합)

+  추가가능한 부분

• [순열] 서로 자리를 바꾸어 순열을 만드는 알고리즘으로 시간복잡도 최소화
• [조합] n개에서 r개를 택할 때, r의 갯수를 하나씩 줄여가며 재귀로 푸는방식 (nCr = n-1Cr-1 + n-1Cr 활용)

 

순열(Permutation)과 조합(Combination)

• 순열 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 순서대로 배열한다.
• 조합 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 그룹을 만든다.

차이점은 순열은 수를 뽑은 후 순서를 생각해야 하지만 조합은 뽑은 것으로 끝난다는 것이다.

내장 패키지 모듈 또는 재귀로 구현할 수 있다.

순열은 어느정도 이해가 되었는데 조합은 조건부분을 아직 완전히 이해하진 못했다.

 

내장 패키지 모듈 사용 - 순열

from itertools import permutations

arr = [1, 2, 3, 4]
print(list(permutations(arr, 3)))

# 4 * 3 * 2 총 24개
# [(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4),
# (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4),
# (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]

 

재귀 사용 - 순열

• 리스트에서 r개를 뽑아 순열로 만든다.
• DFS로 구현한다.

- 글로벌 변수 미사용시 - 

def permutation(arr, r):
    # 사용된 원소를 저장할 배열을 만든다.
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        # 선택리스트에 순열의 원소를 저장하다가 갯수가 r개가 되면 출력 후 함수를 종료한다.
        if len(chosen) == r:
            print(chosen)
            return

        # 반복문을 돌면서
        for i in range(len(arr)):
            # 아직 사용하지 않았다면
            if not used[i]:
                # 선택리스트에 저장하고 방문체크한다.
                chosen.append(arr[i])
                used[i] = 1
                # 다시 generate 함수를 반복한다.
                generate(chosen, used)
                # 하나의 순열이 만들어지면 다시 uncheck한다.
                used[i] = 0
                chosen.pop()

    generate([], used)


permutation([1, 2, 3, 4], 3)

- 글로벌 변수 사용시 - 

def permutation(arr, r):
    global chosen, used

    # 선택리스트에 순열의 원소를 저장하다가 갯수가 r개가 되면 출력 후 함수를 종료한다.
    if len(chosen) == r:
        print(chosen)
        return

    # 반복문을 돌면서
    for i in range(len(arr)):
        # 아직 사용하지 않았다면
        if not used[i]:
            # 선택리스트에 저장하고 방문체크한다.
            chosen.append(arr[i])
            used[i] = 1
            # 다시 generate 함수를 반복한다.
            permutation(arr, r)
            # 하나의 순열이 만들어지면 다시 uncheck한다.
            used[i] = 0
            chosen.pop()


arr = [1, 2, 3, 4]
chosen = []
used = [0 for _ in range(len(arr))]

permutation(arr, 3)

- 전체 순열을 뽑는 경우(r개가 아닌 전체) -

# DFS로 모든 경우의 수를 하나씩 구하되, 각 경우의 수에 같은 요소가 없도록 함으로써 순열을 구현한다

l = ['a', 'b', 'c']
visited = [0 for _ in range(len(l))]
answer = []

def dfs(cnt, list):
    if cnt == len(l):
        answer.append(list[:])
        return

    for i, val in enumerate(l):
        # 만약 방문했다면 건너 뛰기(순열을 위함)
        if visited[i] == 1:
            continue
        # 현재까지의 list에 값을 추가하고, 방문 표시하기
        list.append(val)
        visited[i] = 1

        dfs(cnt+1, list)
        # 방금 전 list에 추가한 값과 방문 한 것을 되돌려주기
        list.pop()
        visited[i] = 0


dfs(0, [])
print(answer)

 

내장 패키지 모듈 사용 - 조합

from itertools import combinations

arr = [1, 2, 3, 4]
print(list(combinations(arr, 3)))

# (4 * 3 * 2) / (3 * 2) 총 4개
# [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

재귀사용 - 조합

• 리스트에서 r개를 뽑아 조합을 만든다.

- DFS 구현 (응??이렇게 간단하다고?) -

l = [1, 2, 3, 4]
n = len(l)
r = 3
answer = []

def dfs(idx, list):
    if len(list) == r:
        answer.append(list[:])
        return

    for i in range(idx, n):
        dfs(i+1,list+[l[i]])

dfs(0, [])
print(answer)

- 글로벌 변수 미사용시 - 

def combination(arr, r):
    # 사용된 원소를 저장할 배열을 만든다.
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    # 선택리스트에 조의 원소를 저장하다가 갯수가 r개가 되면 출력 후 함수를 종료한다.
    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

    	# chosen(뽑은 조합 원소)가 없으면 start = 0으로
        # 그 외에는 뽑은 조합의 가장 마지막 요소를 값의 인덱스 출력
        # arr = [1, 2, 3, 4]
        # 예를들어 chosen = [1, 2]를 뽑은 상태라면 start = arr.index(2) 이므로 1이고
        # 거기에 1을 더해 최종 : 2
        start = arr.index(chosen[-1]) + 1 if chosen else 0
        # nxt = 2부터 시작
        for nxt in range(start, len(arr)):
            # 만약 아직 뽑지 않았고, ~~ 조건이라면
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
            # if used[nxt] == 0 :
                # 다음 요소를 뽑고 방문처리한다.
                chosen.append(arr[nxt])
                used[nxt] = 1
                # 다 뽑았으면 마지막 요소부터 pop하고 방문해제한다.
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])


combination([1, 2, 3, 4], 3)

- 글로벌 변수 사용시 -

def combination(arr, r):
    global chosen, used

    # 선택리스트에 조의 원소를 저장하다가 갯수가 r개가 되면 출력 후 함수를 종료한다.
    if len(chosen) == r:
        print(chosen)
        return

    # chosen(뽑은 조합 원소)가 없으면 start = 0으로
    # 그 외에는 뽑은 조합의 가장 마지막 요소를 값의 인덱스 출력
    start = arr.index(chosen[-1]) + 1 if chosen else 0
    for nxt in range(start, len(arr)):
        # 만약 아직 뽑지 않았고, ~~ 조건이라면
        if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
            # 다음 요소를 뽑고 방문처리한다.
            chosen.append(arr[nxt])
            used[nxt] = 1
            # 다 뽑았으면 마지막 요소부터 pop하고 방문해제한다.
            combination(arr, r)
            chosen.pop()
            used[nxt] = 0


arr = [1, 2, 3, 4]
chosen = []
used = [0 for _ in range(len(arr))]

combination(arr, 3)

코드 참조 : https://ckd2806.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EC%BD%94%EB%93%9C%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

코드 참조 : https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

 

---

중복순열

• 중복순열(n Π r): 서로 다른 n개에서 중복을 허락하여 r개를 선택하여 일렬로 나열한다.
• 예시
  • 서로 다른 편지 3통을 서로 다른 2개의 우체통에 넣는 방법의 수는? 
    • 편지 = (움직이므로) 정의역 r , 우체통 = (움직이지 않으므로)공역  n
    • 정의역에서 공역으로 대응되므로 n Π r =>  2 Π 3  
    • 따라서 8가지
• 파이썬 라이브러리 활용하기

from itertools import product

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

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

 

중복조합

• 중복조합(n H r): 서로 다른 n개에서 중복을 허락하여 r개를 선택한다. (r > n 가능)
• 예시
  • 세 개의 숫자 1, 2, 3에서 중복을 허용하여 6개의 숫자를 선택하는 방법.
    • 6개의 숫자와 (3-1)개의 가림막(구분선) 즉 8개의 자리에 타겟을 놓을 6개의 자리를 택하는 조합의 수
    • 따라서 3H6 = 8C6
    • r개의 타겟과 (n-1)개의 구분선 , nHr = n+r-1Cr 
• 파이썬 라이브러리 활용하기

from itertools import combinations_with_replacement

mylist = [1, 2, 3]
print(list(combinations_with_replacement(mylist, r = 3)))

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