[Python] 순열과 조합

✏️ 수학 공식

순열(Permutation)

• $nPr= { n!\over(n-r)!}$

• 서로 다른 $n$개에서 $r$개를 순서대로 선택하는 경우의 수

조합(Combination)

• $nCr= { n!\over(n-r)! r!}$

• 서로 다른 $n$개에서 $r$개를 순서 상관없이 선택하는 경우의 수

중복 순열(Permutation with repetition)

• $nΠr=n^r$

• 서로 다른 $n$개에서 $r$개를 중복 가능하게 순서로 선택하는 경우의 수

중복 조합(Combination with repetition)

• $nHr= n+r-𝟏Cr = { (n+r-1)!\over(n-1)! r!}$

• 서로 다른 $n$개에서 $r$개를 중복 가능하게 순서 상관없이 선택하는 경우의 수

✏️ Python

재귀함수를 이용한 조합 구현

• 기본적인 아이디어
  combination([0,1,2,3],2) =
  ([0], combination([1,2,3], 1)) +
  ([1], combination([2,3], 1)) +
  ([2], combination([3], 1))
• 코드

def combination(arr,n):
	result = []
	if n == 0:
    	return [[]]
    for i in range(len(arr)):
    	elem = arr[i]
        for rest in combination(arr[i+1:],n-1):
        	result.append([elem] + rest)
    return result

print(combination([0,1,2,3],2)   # [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]   

재귀함수를 이용한 순열 구현

• 기본적인 아이디어
  permutation([0,1,2,3],2) =
  ([0], permuation([1,2,3], 1)) +
  ([1], permuation([0,2,3], 1)) +
  ([2], permuation([0,1,3], 1))+
  ([3], permuation([0,1,2], 1))
• 코드

def permutaion(arr,n):
	result = []
    if n == 0:
    	return [[]]
    for i in range(len(arr)):
    	elem = arr[i]
        for rest permuation(arr[:i] + arr[i+1:], n-1):
        	resutl.append([elem] + rest)
    return result

print(permutation([0,1,2,3],2)   #[[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]

https://kjhoon0330.tistory.com/15