순열, 조합, 중복순열, 중복조합

순열

[1,2,3] 중 2개를 뽑아 순열을 만드는 예시

def dfs(level):
    if level == r:
        print(result)
        return
    
    for i in range(len(arr)):
        if checked[i] == True: continue
        result[level] = arr[i]
        checked[i] = True # 중복순열이 안되게 -> 앞자릿수에서 선택한 값은 뒤에서 선택될 수 없음. 
        dfs(level + 1)
        checked[i] = False # 다시 새로운 result를 만들어낼 때 숫자가 선택될 수 있게
        print(level, checked)

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

 

 

직관적으로 이해될 수 있도록 해당 로직이 돌아가는 순서대로 그림을 그려보았다.

 

입력

[1, 2, 3]

출력

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

 

▪︎ dfs(level)에서 인자 level이 의미하는 바 : arr에서 몇개를 뽑았는지를 의미(= 결과배열에서 몇번째 index까지 값을 채움을 의미), for문을 돌며 결과배열[level]의 값을 업데이트

 

중복순열

[1,2,3] 중 2개를 뽑아 순열을 만드는 예시 (중복 가능)

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

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

 

위의 코드에서 checked 배열을 통해 앞자릿수에서 값이 선택됐는지 확인하는 부분을 주석처리해주면 된다.

 

입력

[1, 2, 3]

출력

[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]

 

조합

[1,2,3,4] 중 2개를 뽑아 조합을 만드는 예시

 

▪︎ 틀린 예시 

def dfs(level, begin):
    if level == r:
        print(result)
        return
    
    for i in range(begin, len(arr)):
        if checked[i] == True: continue
        result[level] = arr[i]
        checked[i] = True
        dfs(level + 1, begin + 1) # 이부분 때문에 틀림 !
        checked[i] = False
arr = [i + 1 for i in range(4)]
r = 2
result = [0] * r
checked = [False] * len(arr)
dfs(0, 0)

 

입력

[1, 2, 3, 4]

출력

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 2]
[3, 4]
[4, 2]
[4, 3]

하늘색 동그라미가 하나의 for문 loop인데, 처음에 재귀로 호출된 begin 값에서 +1이 돼서 각 for문을 돌게 되므로 의도와 다르게 값이 나온다. 처음에 이렇게 짜놓고 왜 틀렸을까 한참을 고민하다 직접 그려봤다 ..

 

▪︎ 맞는 예시 

def dfs(level, begin):
    if level == r:
        print(result)
        return
    
    for i in range(begin, len(arr)):
        if checked[i] == True: continue
        result[level] = arr[i]
        checked[i] = True
        dfs(level + 1, i + 1)
        checked[i] = False
arr = [i + 1 for i in range(4)]
r = 2
result = [0] * r
checked = [False] * len(arr)
dfs(0, 0)

 

입력

[1, 2, 3, 4]

출력

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

dfs()를 재귀호출할 때 for문의 시작범위 인덱스도 함께 넘긴다.

 

중복조합

[1,2,3,4] 중 2개를 뽑아 조합을 만드는 예시 (중복 가능)

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

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

 

입력

[1, 2, 3, 4]

출력

[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[2, 4]
[3, 3]
[3, 4]
[4, 4]

 

조합 코드에서 checked 배열을 통해 앞자릿수에서 해당 수를 이미 썼는지 체크하는 부분을 지우고, 재귀 호출시 begin 부분에 i + 1 대신 i를 넣으면 된다.

 

 

https://toki0411.tistory.com/37

[백트래킹] 조합, 순열, 중복조합, 중복순열 (재귀이용)

https://paris-in-the-rain.tistory.com/35

순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python