Skip to main content

순열과 조합

순열​

  • 순열이란 서로 다른 n개 중에서 r개를 택하는 경우의 수를 의미한다.
  • 1부터 5까지 적힌 카드가 한 장씩 있을 때, 세 장을 뽑아 세 자리 숫자를 만드는 경우의 수
    • 백의 자리에는 5가지의 카드가 올 수 있다.
    • 십의 자리에는 백의 자리에 들어간 카드를 제외한 4가지의 카드가 올 수 있다.
    • 일의 자리에는 백의 자리와 십의 자리에 들어간 카드를 제외한 3가지의 카드가 올 수 있다.
    • 경우의 수는 5∗4∗35 * 4 * 3 총 60가지 이다.
  • n개중에서 r개를 택하는 순열을 기호로 나타내면 nPr_{n}P_{r} 이다.
    • 여기서 P는 순열의 영어 단어인 Permutation의 첫 글자이다.
    • 위의 예시를 기호로 나타내면 5P3_{5}P_{3} 이 된다.
    • nPr_{n}P_{r} = n!(n−r)!n! \over (n-r)!
    • 5P3_{5}P_{3} = 5!(5−3)!5! \over (5-3)!

조합​

  • 조합이란 서로 다른 n개 중에서 r개를 선택하는 경우의 수를 의미한다. 단, 순서는 상관이 없다.
  • 색이 다른 10개의 구슬이 있는데, 그 중 5개를 고르는 경우의 수
    • 위의 순열에서 보인 예처럼 접근하면, 10∗9∗8∗7∗610 * 9 * 8 * 7 * 6 이다.
    • 그러나 순열과는 다르게 a, b, c, d, e 순으로 구슬을 고르거나 b, c, a, d, e 순으로 구슬을 골라도 차이가 발생하지 않는다.
    • 즉, 순서는 다르나 결과는 같은 중복되는 상황은 제거해야 한다.
  • n개중에서 순서와 상관없이 r개를 택하는 조합을 기호로 나타내면 nCr_{n}C_{r} 이다.
    • 여기서 C는 조합의 영어 단어인 Combination의 첫 글자이다.
    • 위의 예시를 기호로 나타내면 10C5_{10}C_{5} 가 된다.
    • nCr_{n}C_{r} = n!(n−r)!∗r!n! \over (n-r)!*r!
    • 10C5_{10}C{5} = 10!(10−5)!∗5!10! \over (10-5)!*5!

파이썬을 이용한 순열과 조합​

재귀로 구현한 순열​

def permutation(s, r):
    if r == 0:
        return ' '
    result = []
    for i, elem in enumerate(s):
        for perm in permutation(s[:i] + s[i+1:], r-1):
            result.append(elem+perm)

    return result


s = 'abc'
print(permutation(s, 2))

## output
## ['ab ', 'ac ', 'ba ', 'bc ', 'ca ', 'cb ']

재귀로 구현한 조합​

def combination(s, r):
    if r == 0:
        return ' '
    result = []
    for i, elem in enumerate(s):
        for comb in combination(s[i + 1:], r-1):
            result.append(elem+comb)

    return result


s = 'abc'
print(combination(s, 2))

## output
## ['ab ', 'ac ', 'bc ']

itertools로 구현한 순열과 조합​

from itertools import permutations
from itertools import combinations

s = 'abc'
print(list(permutations(s,2)))
print(list(combinations(s,2)))

## output
## 순열: [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
## 조합: [('a', 'b'), ('a', 'c'), ('b', 'c')]

나올 수 있는 면접 질문​

  • 순열과 조합 설명
  • 순열과 조합 손 코딩

참고​

기여자​


Junho Moon
📦