순열과 조합💪

유튜버 딩코딩씨 보고 정리해보는 순열과 조합...

재귀, 백트래킹, dfs... 등등 정말 많이 연관되어있어서 정리하면 좋을것 같아 올려봅니다...

##### permutation(순열)

'''
순열 : permutation(포함되어 있는 수가 같은 수여도 순서가 다르면 다른걸로 친다)
dfs 트리와 체크리스트 사용

3개의 공 중에 2개를 뽑는 경우(3P2)
사용한 경우 넣으면 안되므로 체크리스트 사용하는 것임....
깊이 + 1 한후 길이에 맞는 값을 리턴을 하고나면
다시 체크리스트에 빼줘서 다시 넣을 수 있도록 해준다..

1 2
1 3
2 1
2 3
3 1
3 2
6가지
'''

def dfs(L):
    # 종료 조건
    # 리스트의 길이가 찾아야 할 개수(r)가 된다면 종료
    if L == r:
        print(result)
    else:
        for i in range(len(n)):
            # 체크리스트에 해당하는 값이 없다면
            if checklist[i] == 0:
                # result 리스트에 값을 추가
                result[L] = n[i]
                # 체크리스트에 값이 생겼다고 표시해주기
                checklist[i] = 1
                # 다음 깊이로 이동
                dfs(L+1)
                # 다음 번에 다시 사용하기 위해서 빼준다고 그냥 생각하셈 ^^;;;
                checklist[i] = 0

n = [1, 2, 3]
r = 2
result = [0] * r
checklist = [0] * len(n)
dfs(0)

 

이해도 이해지만 어느정도 외울만큼은 외우라고 하심...

이해해야 외우지 싶다가도 이러다가 진도가 영 안나갈거 같아서 적당히 이해시켜서 외우는것이 좋을 듯...

 

'''
조합 : 같은 숫자가 포함되어 있으면 같은 걸로 인정....
순열보다 경우의 수가 훨씬 작음...
순열보다 더 간단...
한번 썼으면 다시 쓰지를 않으니까 체크리스트도 필요없음...
DFS 트리를 이용해서 푼다

3C2

1 2
1 3
2 3

3가지
'''
def dfs(L, BeginWith):
    # 종료 조건
    if L == r:
        print(*result)
    else:
        for i in range(BeginWith, len(n)): # 시작하는 값부터 끝까지
            result[L] = n[i] # 해당하는 값을 넣어주기
            dfs(L+1, i+1) # 다음 깉이 다음 숫자로 이동하여 전 값을 들어오지 못하도록


n = [1, 2, 3]
r = 2
result = [0] * r

dfs(0, 0) # level, begin(어디서 시작할지)