permutation / combination

참고사이트

permutation과 combination은 기본적으로 구현 방법이 같다.

---

combination

combination([1,2,3,4],2) = ([1] + combination([2,3,4],1)) and ([2] + combination([3,4],1)) and ([3] + combination([4],1))

이렇게 재귀적으로 구현 할 수 있다.

아래는 python으로 구현 한 combination 코드다.

def combi(arr, n): 
  result = []
  if n == 1:
    for i in arr:
      result.append([i])
  else :
    for i in range(len(arr)-n+1):
      for next in combi(arr[i+1:],n-1):
        
        result.append([arr[i]]+next)
  
  return result

---

Permutaion

permutation([1,2,3,4],2) = ([1] + permutation([2,3,4],1)) and
([2] + permutation([1,3,4],1)) and ([3] + permutation([1,2,4],1)) and
([4] + permutation([1,2,3],1))

아래는 permutation을 python으로 구현한 코드다.
combination에 대한 이해가 선행된다면 이해가 매우 쉬울 것이다.

def permutation(arr, n): 
  result = []
  if n == 1:
    for i in arr:
      result.append([i])
  else :
    for i in range(len(arr)-n+1):
      temp = [*arr]
      del temp[i]
      for next in permutation(temp,n-1):
        
        result.append([arr[i]]+next)
  
  return result