[알고리즘] 개념 - 순열, 조합, 중복순열, 중복조합 차이

순열 (permutations)
: 서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

• (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

  
  

조합 (combinations)
: 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

• (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

  
  

중복 순열 (product)
: 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수

• (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)

  
  

중복 조합 (combinations_with_replacement)
: 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수

• (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

  
  

순열과 조합의 차이
순열은 : [2,1] 과 [1,2]를 다른 것으로 봄

• nPr = n! // (n-r)!
  조합은 : [2,1] 과 [1,2]를 같은 것으로 봄
• nCr = n! // ((n-r)!*r!)
  ref1. 이론
  ref2. 파이썬 구현