조합, 순열 (Python)

조합

• 서로 다른 n개의 원소에서 r개를 순서에 상관없이 선택하는 것

순열

• 서로 다른 n개의 원소에서 r개를 순서에 상관있게 선택하는 것

차이점

• 조합 → 순서상관X
• 순열 → 순서상관O

예시

• [1,2,3] 중 2가지를 뽑는 경우
• 순열
  • [1,2],[2,1],[1,3],[3,1],[2,3],[3,2]
• 조합
  • [1,2],[1,3],[2,3]

조합 코드

answer = []
def combination(idx,cur,r,lst):
    global answer
    if len(cur) == r:
        answer.append(cur[:])
        return
    for i in range(idx,len(lst)):
        combination(i+1,cur+[lst[i]],r,lst)
combination(0,[],2,[1,2,3])
print(answer)

• 결과
  • [[1, 2], [1, 3], [2, 3]]

순열 코드

answer = []
def permutation(cur,r,lst,visited):
   global answer
   if len(cur) == r:
       answer.append(cur[:])
       return
   for i in range(len(lst)):
       if not visited[i]:
           visited[i] = True
           permutation(cur+[lst[i]],r,lst,visited)
           visited[i] = False
permutation([],2,[1,2,3],[False]*3)
print(answer)

• 결과
  • [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]