순열, 조합 파이썬으로 구현하기 (dfs)

순열

• 서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열
• 선택하는 순서가 다르면 서로 다른 것 (즉, AB와 BA가 다르다)

cards = ['A', 'B', 'C', 'D']
k = 3
visited = [False] * len(cards)
answer = []


def dfs(count, arr):
    if count == k:
        answer.append(arr[:])
        return

    for i, card in enumerate(cards):
        if not visited[i]:
            arr.append(card)
            visited[i] = True
            dfs(count + 1, arr)
            arr.pop()
            visited[i] = False


dfs(0, [])
print(answer)

 

 

중복순열

• 서로 다른 n개의 원소에서 r개를 중복을 허용하여 선택하여 순서대로 나열
• 선택하는 순서가 다르면 서로 다른 것 (즉, AB와 BA가 다르다)

cards = ['A', 'B', 'C', 'D']
k = 3
answer = []


def dfs(count, arr):
    if count == k:
        answer.append(arr[:])
        return

    for i, card in enumerate(cards):
        arr.append(card)
        dfs(count + 1, arr)
        arr.pop()


dfs(0, [])
print(answer)

 

 

조합

• 서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열
• 뽑는 순서와 관계 없음 (즉, AB와 BA가 같다.)

cards = ['A', 'B', 'C', 'D']
k = 3
visited = [False] * len(cards)
answer = []


def dfs(count, start, arr):
    if count == k:
        answer.append(arr[:])
        return
    for i in range(start, len(cards)):
        if not visited[i]:
            arr.append(cards[i])
            visited[i] = True
            dfs(count + 1, i + 1, arr)  # 직전에 뽑은 카드의 다음 index 카드부터 뽑기
            arr.pop()
            visited[i] = False


dfs(0, 0, [])
print(answer)

 

 

중복조합

• 서로 다른 n개의 원소에서 r개를 중복을 허용하여 선택하여 순서대로 나열
• 뽑는 순서와 관계 없음 (즉, AB와 BA가 같다.)

cards = ['A', 'B', 'C', 'D']
k = 3
answer = []


def dfs(count, start, arr):
    if count == k:
        answer.append(arr[:])
        return
    for i in range(start, len(cards)):
        arr.append(cards[i])
        dfs(count + 1, i, arr)  # 직전에 뽑은 카드와 같은 index부터 뽑기
        arr.pop()


dfs(0, 0, [])
print(answer)