순열, 조합 - 2탄

1-1. 순열

▪︎ itertools 사용

permutations(iterable, r =  None) : iterable에서 원소 개수가 r개인 순열 뽑기

from itertools import permutations

arr = ['A', 'B', 'C']

# r을 지정하지 않거나 r = None으로 하면 최대 길이의 순열 리턴
for i in permutations(arr): 
	print(i)
    
'''
출력결과:
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')
'''

▪︎ 백트래킹

• 1, 2, 3, != 3, 2, 1이므로 이전에 방문했던 곳도 재방문 해야 함.
  -> visited 방문 여부 표시 필요 O

1) append, pop 

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = []
checked = [False] * len(arr)

def dfs(level):
	if level == r:
    	print(result)	
        return
    
    for i in range(len(arr)):
    	if checked[i] == False:
        	checked[i] = True            
            result.append(arr[i])
            dfs(level + 1)
            checked[i] = False
            result.pop()

dfs(0)

2)  result 배열에 바로 쓰기

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = [0] * r
checked = [False] * len(arr)

def dfs(level):
	if level == r:
    	print(result)	
        return
    
    for i in range(len(arr)):
    	if checked[i] == False:
        	checked[i] = True            
            result[level] = arr[i]
            dfs(level + 1)
            checked[i] = False

dfs(0)

---

1-2. 중복 순열

▪︎ itertools 사용

product(*iterables, repeat = 1) : 여러 iterable의 데카르트곱 리턴

product는 다른 함수와 달리 인자로 여러 iterable을 넣어줄 수 있고, 이들 간의 모든 짝을 지어서 리턴한다.

 

for i in product(arr1,repeat=3): #product(arr1, arr1, arr1, repeat=1)과 동일한 출력
	print(i)

'''
출력결과:
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'B', 'A')
('A', 'B', 'B')
('B', 'A', 'A')
('B', 'A', 'B')
('B', 'B', 'A')
('B', 'B', 'B')
'''

 

▪︎ 백트래킹

1) append, pop 

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = []

def dfs(level):
    if level == r:
        print(result)	
        return
    
    for i in range(len(arr)):
        result.append(arr[i])
        dfs(level + 1)
        result.pop()

dfs(0)

2)  result 배열에 바로 쓰기

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = [0] * r

def dfs(level):
    if level == r:
        print(result)	
        return
    
    for i in range(len(arr)):
        result[level] = arr[i]
        dfs(level + 1)

dfs(0)

 

---

2-1. 조합

▪︎ itertools 사용

combinations(iterable, r): iterable에서 원소 개수가 r개인 조합 뽑기 

from itertools import combinations

arr = [1, 2, 3]

for i in combinations(arr, 2):
	print(i)

'''
출력 결과:
(1, 2)
(1, 3)
(2, 3)
'''

 

파이썬 공식문서에 따르면 입력 iterable이 정렬되어 있으면, 조합 튜플이 정렬된 순서로 생성된다.

▪︎ 백트래킹

• 1, 2, 3, == 3, 2, 1이므로 이전에 방문했던 곳은 재방문할 필요 없음.
  -> visited 방문 여부 표시 필요 X

1) append, pop 

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = []

def dfs(begin, level):
    if level == r:
        print(result)	
        return
    
    for i in range(begin, len(arr)):     
            result.append(arr[i])
            dfs(i + 1, level + 1)
            result.pop()

dfs(0, 0)

2)  result 배열에 바로 쓰기

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = [0] * r

def dfs(begin, level):
	if level == r:
    	print(result)	
        return
    
    for i in range(begin, len(arr)):     
            result[level] = arr[i]
            dfs(i + 1, level + 1)

dfs(0, 0)

---

2-2. 중복 조합

▪︎ itertools 사용

combinations_with_replacement(iterable, r): iterable에서 원소 개수가 r개인 중복 조합 뽑기

from iterable import combinations_with_replacement

arr = ['A', 'B', 'C']

for i in combinations_with_replacement(arr, 2):
	print(i)

'''
출력 결과:
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'B')
('B', 'C')
('C', 'C')
'''

▪︎ 백트래킹

1) append, pop 

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = []

def dfs(begin, level):
    if level == r:
        print(result)	
        return
    
    for i in range(begin, len(arr)):     
            result.append(arr[i])
            dfs(i, level + 1)
            result.pop()

dfs(0, 0)

2)  result 배열에 바로 쓰기

arr = [i + 1 for i in range(3)] # 1, 2, 3
r = 2
result = [0] * r

def dfs(begin, level):
    if level == r:
        print(result)	
        return
    
    for i in range(begin, len(arr)):     
            result[level] = arr[i]
            dfs(i, level + 1)

dfs(0, 0)

---

* itertools - product (데카르트의 곱)

from itertools import product

arr1 = ['A', 'B']
arr2 = ['1', '2']

for i in product(arr1, arr2, repeat = 1):
	print(i)

'''
출력결과:
('A', '1')
('A', '2')
('B', '1')
('B', '2')
'''

from itertools import product

# 각 종류의 항목 리스트
category1 = ['사과', '바나나', '체리']
category2 = ['빨강', '노랑', '초록']
category3 = ['작은', '중간', '큰']

# 모든 조합 생성
combinations = list(product(category1, category2, category3))

for i in combinations:
    print(i)
    
'''
출력 결과:
('사과', '빨강', '작은')
('사과', '빨강', '중간')
('사과', '빨강', '큰')
('사과', '노랑', '작은')
('사과', '노랑', '중간')
...
('체리', '초록', '큰')
'''

 

1. 데카르트 곱 의미

• product는 데카르트의 곱을 생성한다.
• 데카르트의 곱이란, 두 집합 A와 B에 대해 모든 가능한 순서쌍 (a,b)를 만드는 연산이다.

2. 순열과의 차이

• 순서를 고려하지 않는 조합이 아니라, 두 리스트에서 각각 하나씩 선택한 결과이다.
• product는 중복순열과도 다른 연산이다. 그 이유는 각 리스트가 독립적으로 선택되기 때문이다.
• 하지만, repeat을 2 이상으로 설정하고, 자기 자신을 iterable로 넣으면 이는 중복순열을 생성하는 동작이 된다.

---

참고 문헌

https://seu11ee.tistory.com/5

[파이썬] itertools 라이브러리 사용법 (순열, 조합)(permutations, combinations) - Python 문법

https://juhee-maeng.tistory.com/entry/Python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4-%EC%A4%91%EB%B3%B5%EC%A1%B0%ED%95%A9-%EC%89%BD%EA%B2%8C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

(Python) 순열, 조합, 중복순열, 중복조합 쉽게 구현하기

https://velog.io/@kjyeon1101/%EC%BD%94%ED%85%8C-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9%EA%B3%BC-%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9

[코테] 백트래킹과 순열/조합