[Python/DailyAlgo] 99, 100, 101, 102. 순열, 조합, 중복순열, 중복조합

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

순열과 조합

 

https://dailyalgo.kr/ko/problems/99

https://dailyalgo.kr/ko/problems/100

https://dailyalgo.kr/ko/problems/101

https://dailyalgo.kr/ko/problems/102

순열과 조합 기본 유형 4문제라서 한꺼번에 묶었습니당~~~

---

순열

재귀로 직접 구현 풀이

def solution(n, m):

    def permutations(current):
        # 만약 목표 길이 도달했으면 -> return
        # 아니라면 -> 계속 함수 실행
        if len(current) == m:
            # 참고로, 여기서 객체에다가 append 하는 거니까 값을 수정하는 게 아니기에,
            # nonlocal answer은 필요 없음. 할당이 아니잖음. 

            # 여기 얕은 복사 해서 current와 같은 약은 복사 객체를 넣으면 됨.
            answer.append(current[:])

            # 아래처럼 했다면 그냥 '할당'이 돼버려서,
            # answer[0]와 current가 같은 객체를 가리키는 변수가 돼버림.
            # 정확히는, current가 가리키고 있는 같은 객체를 answer에 append 하는 것.
            # answer.append(current)

            return
        
        # 사실상, 이게 취소한 것만 제외하면, 인접 리스트로 dfs 하는 거랑 똑같음 원리는
        # 아닌 경우니까 -> 계속 함수 실행해야 함.
        for i in range(1, n + 1):
            # 아직 안 고른 수면 -> 추가하고 함수 실행
            if not visited[i]:
                # 일단 방문처리
                visited[i] = True
                current.append(i)
                permutations(current)
                # 뽑은 놈들 취소하기
                visited[i] = False
                current.pop()

                # 중요!!! 여기 단계에서 실행하면 틀림. 
                # 얕은 복사가 필요한데, 그렇지 못해서, current가 저장된 모든 곳의 current가
                # 같은 객체를 가리키는 변수였던 거임.

                # 즉, 아래의 current와, answer[0]은 둘 다 똑같이 [1, 2]라는 동일한 객체를
                # 포인팅하고 있는, 가리키고 있는 변수임.

                # 즉, answer에 이미 append된 current가 아래 코드에서 같이 pop됨.
                # current를 pop하니, answer[0] == [1, 2]가 [1]이 되고, 다시 []이 되는 거임.

                # 따라서, 위에 answer에 넣을 때, 얕은 복사를 해서 넣으면 됨.

    
    # numbers = [i for i in range(1, n+1)] -> 필요없어짐.
    length = m
    visited = [False] * (n + 1)

    answer = []
    permutations([])
    # 참고로, 우린 따로 정렬할 필요가 x.
    # 어차피 사전순대로 뽑게 되니까.
    return answer


# [1, 2, ..., n]에 대해, nPm으로 가능한 모든 순열의 경우를 구하여라.

# answer = []
# current = [1, 2, 3]
# answer.append(current)

# -> answer[0], current는 둘 다 [1, 2, 3]이라는 객체를 가리키는 변수임.

itertools 모듈 사용 풀이

from itertools import permutations
def solution(n, m):
    return [list(permutation) for permutation in permutations(range(1, n+1), m)]

---

250222 재풀이

재귀로 직접 구현 풀이

def solution(n, m):

    def permutations(current):
        # 1. 뽑고 싶은 만큼 뽑았다면 종료한다.
        if len(current) == m:
            answer.append(current[:])
            return
        # 2. 그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.
        for i in range(1, n + 1):
            if not visited[i]:
                visited[i] = True
                current.append(i)
                permutations(current)
                visited[i] = False
                current.pop()

    visited = [False] * (n + 1)
    answer = []
    
    permutations([])
    return answer

itertools 모듈 사용 풀이

from itertools import permutations
def solution(n, m):
    
    # return = list(map(list, permutations(range(1, n + 1), m)))
    return [list(permutation) for permutation in permutations(range(1, n + 1), m)]

조합

재귀로 직접 구현 풀이

def solution(n, m):

    def combinations(current, start):
        if len(current) == m:
            # 얕은 복사
            answer.append(current[:])
            return
        for i in range(start, n + 1): # start ~ n까지이니까
            current.append(i) # start ~ n까지이니까
            combinations(current, i + 1)
            current.pop()

    answer = []
    combinations([], 1)
    return answer

# [1, 2, ..., n]에 대해, nCm을 한 모든 경우를 반환하라.

 

---

250222 재풀이

재귀로 직접 구현 풀이

def solution(n, m):

    def combinations(current, start):
        # 1. 뽑고 싶은 만큼 뽑았다면 종료한다.
        if len(current) == m:
            answer.append(current[:])
            return
        # 2. 그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.
        for i in range(start, n + 1):
            current.append(i)
            combinations(current, i + 1)
            current.pop()


    answer = []
    combinations([], 1)
    return answer

itertools 모듈 사용 풀이

from itertools import combinations
def solution(n, m):
    return [list(combination) for combination in combinations(range(1, n + 1), m)]

중복순열

재귀로 직접 구현 풀이

def solution(n, m):

    def product(current):
        # 만약 길이가 이미 다 찼으면:
        if len(current) == m:
            # 얕은 복사해서 current 집어넣음
            answer.append(current[:])
            # 다음 꺼 다룰 수 있게 return
            return
        # 만약 길이가 아직 다 안 찼으면:
        for i in range(1, n + 1): # 1 ~ n 숫자로
            # 중복 순열이니 i 앞에서부터 집어넣고
            current.append(i)
            # 그 집어넣어진 current로 다시 중복 순열 돌림
            product(current)
            # 그리고 다른 거 고려해줘야 하니까, pop 해야함
            current.pop()



    answer = []
    product([])
    return answer

# 1, 2, ..., n 중에서 m개를 중복 순열로 선택하는 숫자 집합 반환
# n파이m을 구해라.

 

---

250222 재풀이

재귀로 직접 구현 풀이

def solution(n, m):
    def product(current):
        # 1. 뽑을 만큼 뽑았다면 종료
        if len(current) == m:
            answer.append(current[:])
            return
        # 2. 그렇지 않다면, 재귀 돌며 계속 수를 뽑음.
        for i in range(1, n + 1):
            current.append(i)
            product(current)
            current.pop()

    answer = []
    product([])
    return answer

itertools 모듈 사용 풀이

from itertools import product
def solution(n, m):
    return [list(prod) for prod in product(range(1, n + 1), repeat = m)]

중복조합

재귀로 직접 구현 풀이

def solution(n, m):
    
    def combinations_with_replacement(current, start):
        if len(current) == m:
            answer.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            combinations_with_replacement(current, i)
            current.pop()



    answer = []
    combinations_with_replacement([], 1)
    return answer

# 1, 2, ..., n 중에서 m개의 숫자를 뽑을 건데,
# 보면 지금 순서를 고려하지 않고 뽑는 거임.
# 근데 중복은 허용함. 중복 조합 문제.
# 즉, nHm의 모든 가능한 숫자 집합을 반환하면 됨.

 

---

250222 재풀이

재귀로 직접 구현 풀이

def solution(n, m):

    def combinations_with_replacement(current, start):
        # 1. 뽑고 싶은 만큼 뽑았다면 종료
        if len(current) == m:
            answer.append(current[:])
            return
        # 2. 그렇지 않다면, 재귀 돌며 수를 계속 뽑음.
        for i in range(start, n + 1):
            current.append(i)
            combinations_with_replacement(current, i)
            current.pop()

    answer = []
    combinations_with_replacement([], 1)
    return answer

itertools 모듈 사용 풀이

from itertools import combinations_with_replacement
def solution(n, m):
    return [list(combination) for combination in combinations_with_replacement(range(1, n + 1), m)]