순열, 조합

Computer Science/Algorithm

순열, 조합 - 2탄

_은선_ 2025. 1. 27. 16:30

SMALL

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)
    
'''
출력 결과:
('사과', '빨강', '작은')
('사과', '빨강', '중간')
('사과', '빨강', '큰')
('사과', '노랑', '작은')
('사과', '노랑', '중간')
...
('체리', '초록', '큰')
'''