[Python] 파이썬 순열과 조합, 중복 순열과 중복 조합

 

파이썬 내장 모듈인 itertools를 활용하여 순열과 조합, 중복 순열을 쉽게 구현할 수 있다.

순열과 조합은 재귀 함수나 반복문을 이용해서 직접 구현할 수도 있지만, 코딩테스트에서 직접 구현하는 것은 번거롭기도 하고, 라이브러리를 사용하는 것이 훨씬 속도도 빠르다.

 

 

---

1. 순열

- 순열이란?

• 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것을 말한다.
• 뽑힌 순서대로 나열하기 때문에 순서가 의미가 있다. 즉, 같은 값이 뽑히더라도 순서가 다르면 다른 경우의 수로 취급한다.
  예를 들어 (1, 2)와 (2, 1)은 다른 것으로 취급한다.

- itertools 라이브러리의 permutations 함수를 이용한 코드 구현

from itertools import permutations

data = [1, 2, 3, 4]

for nums in permutations(data, 2):
    print(nums, end=" ")



# 결과
(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

 

2. 조합

- 조합이란?

• 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것을 의미한다.
• 순서가 의미가 없기 때문에 중복을 허용하지 않고 r개를 뽑는다.
  예를 들어 (1, 2)와 (2, 1)은 같은 것으로 취급한다. 따라서 (1, 2)만 존재한다.

- itertools 라이브러리의 combinations를 이용한 코드 구현

from itertools import combinations

data = [1, 2, 3, 4]

for nums in combinations(data, 2):
    print(nums, end=" ")
    
    
# 결과
(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

 

3. 중복 순열

- 중복 순열이란?

• 중복 가능한 n개 중에 r개를 나열하는 경우의 수(순서 O)를 말한다.
• itertools의 product 함수를 이용하여 두 개 이상의 리스트에서 모든 조합을 계산할 수도 있다.

- case1

from itertools import product

data1 = [1, 2, 3, 4]

for x in product(data1, repeat=2):
    print(x)
    
    
# 결과
(1, 1) (1, 2) (1, 3) (1, 4) (2, 1) (2, 2) (2, 3) (2, 4)
(3, 1) (3, 2) (3, 3) (3, 4) (4, 1) (4, 2) (4, 3) (4, 4)

여기서 repeat=2라는 것은 리스트 [1, 2, 3, 4]와 또 다른 리스트 [1, 2, 3, 4]에서 중복 순열을 뽑는 다는 것을 의미한다.

 

- case2

from itertools import product

data1 = [1, 2, 3, 4]

for x in product(data1, repeat=3):
    print(x)
    
    
# 결과
(1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 1, 4) (1, 2, 1) (1, 2, 2) (1, 2, 3) (1, 2, 4) 
(1, 3, 1) (1, 3, 2) (1, 3, 3) (1, 3, 4) (1, 4, 1) (1, 4, 2) (1, 4, 3) (1, 4, 4) 
(2, 1, 1) (2, 1, 2) (2, 1, 3) (2, 1, 4) (2, 2, 1) (2, 2, 2) (2, 2, 3) (2, 2, 4) 
(2, 3, 1) (2, 3, 2) (2, 3, 3) (2, 3, 4) (2, 4, 1) (2, 4, 2) (2, 4, 3) (2, 4, 4) 
(3, 1, 1) (3, 1, 2) (3, 1, 3) (3, 1, 4) (3, 2, 1) (3, 2, 2) (3, 2, 3) (3, 2, 4) 
(3, 3, 1) (3, 3, 2) (3, 3, 3) (3, 3, 4) (3, 4, 1) (3, 4, 2) (3, 4, 3) (3, 4, 4) 
(4, 1, 1) (4, 1, 2) (4, 1, 3) (4, 1, 4) (4, 2, 1) (4, 2, 2) (4, 2, 3) (4, 2, 4) 
(4, 3, 1) (4, 3, 2) (4, 3, 3) (4, 3, 4) (4, 4, 1) (4, 4, 2) (4, 4, 3) (4, 4, 4)

여기서 repeat=3라는 것은 리스트 [1, 2, 3, 4]와 또 다른 리스트 [1, 2, 3, 4]와 또 다른 리스트 [1, 2, 3, 4]에서 중복 순열을 뽑는 다는 것을 의미한다.

 

- case3

from itertools import product

data1 = [1, 2, 3, 4]
data2 = 'abc'

for x in product(data1, data2):
    print(x, end=" ")


# 결과
(1, 'a') (1, 'b') (1, 'c') (2, 'a') (2, 'b') (2, 'c') 
(3, 'a') (3, 'b') (3, 'c') (4, 'a') (4, 'b') (4, 'c')

 

4. 중복 조합

- 중복 조합이란?

• 중복 가능한 n개 중에 r개를 선택하는 경우의 수(순서 X)를 말한다.

- combinations_with_replacement 함수를 이용한 코드 구현

from itertools import combinations_with_replacement

data = [1, 2, 3, 4]

for x in combinations_with_replacement(data, 2):
    print(x, end=" ")


# 결과
(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)