[ Python Skill ] Python에서 순열과 조합 사용하기

(2019.11.22일에 내용을 보강했습니다.)

이번 포스팅에서는 파이썬에서 순열과 조합을 사용하는 방법에 대해서 알아보겠습니다.

 

1. 순열

순열을 순서대로 뽑는 것을 나타내며 nPr로 표기합니다. (n은 전체 갯수, r은 뽑는 갯수)

만약 1, 2, 3, 4 중 2개의 숫자를 뽑아 자연수를 만드는 경우, 12, 21... 등이 나올 것이고 이런 경우를 4P2로 표기합니다.

 

C++의 <algorithm> 헤더에 next_permutation 함수가 있듯이 파이썬에는 itertools 모듈에 permutations 함수가 있어 순열을 쉽게 구현할 수 있습니다. 예시 코드를 보도록하겠습니다.

 

from itertools import permutations

items = ['A', 'B', 'C', 'D']
print(list(map(''.join, permutations(items))))  # items의 모든 원소를 가지고 순열을 만든다.
print(list(map(''.join, permutations(items, 2))))  # 2개의 원소를 가지고 순열을 만든다

>>['ABCD', 'ABDC', 'ACBD', 'ACDB', 'ADBC', 'ADCB', 'BACD', 'BADC', 'BCAD', 'BCDA', 'BDAC', 'BDCA', 'CABD', 'CADB', 'CBAD', 'CBDA', 'CDAB', 'CDBA', 'DABC', 'DACB', 'DBAC', 'DBCA', 'DCAB', 'DCBA']

>> ['AB', 'AC', 'AD', 'BA', 'BC', 'BD', 'CA', 'CB', 'CD', 'DA', 'DB', 'DC']

 

 

2. 조합

조합은 순열과 다르게 뽑아서 순서대로 나열하는 것이 아니라 뽑기만 하는 경우입니다.

순열에서 예로 들었던 1, 2, 3 , 4 중 2개의 숫자를 뽑아 자연수를 만드는 경우 12, 21이 순열에서는 나오지만 조합에서는 12만 나오게 됩니다.

 

조합을 구하는 combinations 함수는 아이템과 만들려는 조합의 갯수가 필수적이다.

from itertools import combinations

items = ['A', 'B', 'C', 'D']
for i in range(1, len(items)):
    print(list(map(''.join, combinations(items, i))))  # 조합을 만들려는 아이템과 조합의 수를 반드시넘겨줘야한다.

>>['A', 'B', 'C', 'D']
['AB', 'AC', 'AD', 'BC', 'BD', 'CD']
['ABC', 'ABD', 'ACD', 'BCD']

 

 

3. 순열과 조합의 차이 

순열과 조합의 개념을 설명하며 예로 들었던 4개의 숫자중에 2개를 뽑아 자연수를 만드는 경우를 코드와 출력결과를 통해 살펴보겠습니다.

 

iterable_list = ['1', '2', '3', '4']
print('순열 : ', list(map(''.join, itertools.permutations(iterable_list, 2))))
print('조합 : ', list(map(''.join, itertools.combinations(iterable_list, 2))))

>> 순열 : ['12', '13', '14', '21', '23', '24', '31', '32', '34', '41', '42', '43']

조합 : ['12', '13', '14', '23', '24', '34']

 

출력결과를 보시면 순열과 조합의 차이를 명확하게 아실 수 있습니다.

순열은 순서대로 나열하기 때문에 '12'와 '21'은 다른 케이스로 봅니다. 하지만 조합은 뽑기만 하기 때문에 '12'와 '21'은 같은 케이스로 구분하게 됩니다. 그래서 '12'만 결과에 나오게 됩니다.

 

 

* 응용 1 - 2019 카카오 신입 공채 1차 코딩 테스트 후보키 문제

 

후보키가 될 수 있는 모든 조합 만들기 

from itertools import combinations, permutations

relations = [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
combi_result = []

for relation in relations:
    for i in range(1, len(relation)):
        for c in combinations(relation, i):
            combi_result.append(c)

print(combi_result)

>> [('100',), ('ryan',), ('music',), ('2',), ('100', 'ryan'), ('100', 'music'), ('100', '2'), ('ryan', 'music'), ('ryan', '2'), ('music', '2'), ('100', 'ryan', 'music'), ('100', 'ryan', '2'), ('100', 'music', '2'), ('ryan', 'music', '2'), ('200',), ('apeach',), ('math',), ('2',), ('200', 'apeach'), ('200', 'math'), ('200', '2'), ('apeach', 'math'), ('apeach', '2'), ('math', '2'), ('200', 'apeach', 'math'), ('200', 'apeach', '2'), ('200', 'math', '2'), ('apeach', 'math', '2'), ('300',), ('tube',), ('computer',), ('3',), ('300', 'tube'), ('300', 'computer'), ('300', '3'), ('tube', 'computer'), ('tube', '3'), ('computer', '3'), ('300', 'tube', 'computer'), ('300', 'tube', '3'), ('300', 'computer', '3'), ('tube', 'computer', '3'), ('400',), ('con',), ('computer',), ('4',), ('400', 'con'), ('400', 'computer'), ('400', '4'), ('con', 'computer'), ('con', '4'), ('computer', '4'), ('400', 'con', 'computer'), ('400', 'con', '4'), ('400', 'computer', '4'), ('con', 'computer', '4'), ('500',), ('muzi',), ('music',), ('3',), ('500', 'muzi'), ('500', 'music'), ('500', '3'), ('muzi', 'music'), ('muzi', '3'), ('music', '3'), ('500', 'muzi', 'music'), ('500', 'muzi', '3'), ('500', 'music', '3'), ('muzi', 'music', '3'), ('600',), ('apeach',), ('music',), ('2',), ('600', 'apeach'), ('600', 'music'), ('600', '2'), ('apeach', 'music'), ('apeach', '2'), ('music', '2'), ('600', 'apeach', 'music'), ('600', 'apeach', '2'), ('600', 'music', '2'), ('apeach', 'music', '2')]

 

=> 모든 조합을 구해준 후 , 유일성과 최소성을 만족하는 후보키를  구하면 된다.

 

* 응용 2 - 소수 찾기 

입력값으로 숫자 리스트가 주어지거나 "17"과 같은 문자열 형식의 숫자가 주어지고 주어진 입력값의 모든 조합의 숫자를 구해 소수를 찾는 문제는 다양한 문제에서 많이 출시됩니다.

 

이런 경우 순열을 사용해 모든 조합을 구한 후 소수를 찾아주면 됩니다.

특히 소수를 찾을 때 아래와 같이 for 문을 통해 소수를 구할 수도 있지만 '에라토스테네스의 체'를 통해 소수를 판별할 수 있습니다.

 

<코드>

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, num): 
        if num % i == 0:
            return False
    return True

 

- 에라토스테네스의 체 

에라토스테네스의 체는 소수를 찾는 방법 중의 하나입니다. 소수를 찾는 방법은 아래와 같습니다.

1) 2의 배수를 지웁니다.

2) 3의 배수를 지웁니다.

3) 4의 배수를 지웁니다.

.. 위의 과정을 반복하며 배수들을 지워 나가다 보면 구하는 구간의 모든 소수만 남게 됩니다.

 

<코드 >

# 에라토스테네스의 체

# n은 구하고자 하는 구간의 길이
def eratos(n): 
    prime_check = [False, False] + [True] * (n - 1) # 소수인지 아닌지 판별한 값을 저장하는 리스트 (소수 : True ) / 0,1은 소수 X
    primes = list() # 소수들을 담을 리스트
    for i in range(2, int(n ** 0.5) + 1): # 2부터 n ** 0.5(배수를 해주기 때문에)까지 루프를돕니다. 
        for j in range(i*2, n+1, i): # 2의 배수, 3의 배수를 지워나갑니다. 
            prime_check[j] = False
            
    for idx, flag in enumerate(prime_check): # 소수인 것들만 primes 리스트에 추가해줍니다.
        if flag:
            primes.append(idx)
    
    return primes

print(eratos(121))

>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

 

레퍼런스 

[1] Python Cookbook, 3rd edition, by David Beazely abnd Brian K, Jones (O'Reilly)

[2] https://programmers.co.kr/learn/courses/4008/lessons/12836

파이썬을 파이썬답게 - 순열과 조합 - combinations, permutations | 프로그래머스

[3] 순열과 조합 : https://m.blog.naver.com/PostView.nhn?blogId=freewheel3&logNo=220763729760&proxyReferer=https%3A%2F%2Fwww.google.com%2F

순열 nPr, 조합과의 차이를 포켓몬으로 알아보자

[4]https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

[5] 에라토스테네스의 체 1 : https://wikidocs.net/21638

위키독스