순열 (Permutation)
순열은 집합에서 원소들을 선택하여 순서를 고려하여 나열하는 것을 말합니다. n개의 원소가 있는 집합에서 r개를 선택하여 나열하는 경우의 수는 nPr로 표현합니다. 이 경우의 수는 다음과 같이 구할 수 있습니다.
nPr = n! / (n-r)!예를 들어, {1, 2, 3}이라는 세 개의 원소를 가진 집합에서 2개의 원소를 선택하여 나열하는 경우의 수는 다음과 같습니다.
3P2 = 3! / (3-2)! = 3이러한 순열은 주어진 원소들의 순서도 중요한 경우에 사용됩니다. 예를 들어, {A, B, C}라는 세 개의 원소에서 2개를 선택하여 나열하는 경우, 가능한 모든 순열은 {AB, AC, BA, BC, CA, CB}입니다.
조합 (Combination)
조합은 집합에서 원소들을 선택하여 순서를 고려하지 않고 나열하는 것을 말합니다. n개의 원소가 있는 집합에서 r개를 선택하여 나열하는 경우의 수는 nCr로 표현합니다. 이 경우의 수는 다음과 같이 구할 수 있습니다.
nCr = n! / (r! * (n-r)!)예를 들어, {1, 2, 3}이라는 세 개의 원소를 가진 집합에서 2개의 원소를 선택하여 나열하는 경우의 수는 다음과 같습니다.
3C2 = 3! / (2! * (3-2)!) = 3조합은 주어진 원소들의 순서가 중요하지 않고, 단지 선택된 원소의 개수에만 관심이 있는 경우에 사용됩니다. 예를 들어, {A, B, C}라는 세 개의 원소에서 2개를 선택하여 나열하는 경우, 가능한 모든 조합은 {AB, AC, BC}입니다.
순열과 조합의 예제 구현
아래는 순열과 조합을 구현한 예제입니다. 예제에서는 주어진 원소들의 배열과 선택할 개수를 입력으로 받아, 가능한 순열과 조합을 출력합니다.
def permutation(arr, r):
result = []
if r == 0:
return [[]]
for i in range(len(arr)):
pick = arr[i]
rest = arr[:i] + arr[i+1:]
for p in permutation(rest, r-1):
result.append([pick] + p)
return result
def combination(arr, r):
result = []
if r == 0:
return [[]]
for i in range(len(arr)):
pick = arr[i]
rest = arr[i+1:]
for c in combination(rest, r-1):
result.append([pick] + c)
return result
# 예제 실행
elements = ['A', 'B', 'C']
print(permutation(elements, 2))
print(combination(elements, 2))위의 코드는 주어진 원소들의 배열 arr과 선택할 개수 r을 입력으로 받아, 재귀적으로 순열과 조합을 생성하는 permutation과 combination 함수를 정의하고 있습니다. 각 함수는 r이 0일 때는 빈 리스트 []를 반환하고, 그 외의 경우에는 arr에서 한 개의 원소를 선택하고 나머지 원소들에 대해 재귀적으로 순열이나 조합을 생성하여 결과 리스트에 추가합니다.
예제에서는 {A, B, C}라는 세 개의 원소에서 2개의 원소를 선택하여 순열과 조합을 생성하고 출력합니다. 순열의 경우 결과는 [[A, B], [A, C], [B, A], [B, C], [C, A], [C, B]]이고, 조합의 경우 결과는 [[A, B], [A, C], [B, C]]입니다.
마무리
순열과 조합은 원소들을 선택하여 나열하는 경우의 수를 계산할 때 유용하게 사용할 수 있는 개념입니다. 순열은 원소들의 순서까지 고려하며, 조합은 순서를 고려하지 않고 원소의 선택 개수에만 관심이 있습니다. 이러한 개념을 통해 원하는 문제에 대한 해답을 구할 수 있습니다.
댓글