[알고리즘 파이썬] 순열과 조합

https://pythontutor.com/

Python Tutor: Learn Python, JavaScript, C, C++, and Java programming by visualizing code

 

- 순열과 조합은 순서 유무의 차이

 

재귀 or 포문 (재귀 이해가 중요!)

 

 

조합

= 칸막이 개념 

== 이중 for문 

백트래킹? == 유망하지 않은걸 안한다 (안되는거 연산 안함)

# 그냥 조합 2개뽑기
arr = ['A', 'B', 'C']
for i in range(3):
    for j in range(i+1, 3):
        print(arr[i], arr[j])

# 중복조합 2개뽑기
arr = ['A', 'B', 'C']
for i in range(3):
    for j in range(i, 3):
        print(arr[i], arr[j])

 

 

순열

arr = ['A', 'B', 'C']

for i in range(3):
    for j in range(3):
        for k in range(3):
            if i != j and j != k and k != i:
								print([arr[i], arr[j], arr[k]])

이 로직은 쓸데없는 연산도 한다.

 

따라서, 재귀가 필요함

 

재귀순열

arr = ['A', 'B', 'C']  # 재료 리스트
sel = [0, 0, 0]  # 인형뽑기 selection
check = [0, 0, 0]  # 뽑을지 말지 결정하는 리스트


def perm(depth):  # 각자 뎁스에서는? 
    if depth == 3:  # 최고 뎁스에 도달했으면? # if depth == len(sel)
        print(sel)  # print
        return

    for i in range(3):  # 3번의 화살표 떨어트릴 기회
        if not check[i]:  # 각 기회 안에서 check를 보고 멈출 수 있는지 보고?
            check[i] = 1  # 멈출 수 있다면 if 통과했으니까 자리 차지했다고 표시하고
            sel[depth] = arr[i]  # 화살표가 떨어진 위치의 재료리스트
            perm(depth+1)
            check[i] = 0  # 돌아나오면서 다시 다음을 위해 초기화!! (중요)

perm(0)

 

- 1번째 process : check를 보고 if check가 비어있으면 동그라미 (가져간다) sel에 1에 채워진다 check = [1 0 0]

- 2번째 : 1이 확정된 세상에서 화살표를 던진 다음에 / check를 보고 멈출지 말지 결정 (비어있으면 동그라미) sel 두번째 칸에 채우기 check = [1 1 0]

- 3번째 : 1,2칸이 확정된 세상에서 화살표 던지고 / check를 보고 비어있으면 쓴다고 기록 (check) 확정해서 sel 세번째 칸에 가져간 다음 process 종료 check = [1 1 1 ]

- 4번째 : 프린트실 (그때의 sel 모습을 찍어서 기록한다) sel = [A B C] 

- 프린트실에서 찍은 다음? 5번째 : 다시 올라가 but 3번째 칸은 이미 할 거 다 했기 때문에, return 시킴 (확정 해제) -> check 표시가 풀림 check = [1 1 0 ]

- 6번째 : 2번째 칸으로 올라가보니 이미 고른 거 있는데 그건 확정 해제 check = [1 0 0], 대신 안 해본 옆으로 넘어감 check 배열을 봄 -> 근데 check = [1 0 0 ] 이니 c 가능 >> check = [1 0 1]

- 7번째 : 3번째 칸 다시 가 >> check = [1 0 1] b 비었네? 가져가 check = [1 1 1]

- 8번째 : 프린트실 (sel 찍음) sel = [A C B] 

- 9번째 : return 올라가 > 확정해제 check = [1 1 0]

- 10번째 : return 올라가 > 확정해제 check = [1 0 0 ]

- 11번째 : reutrn 올라가 > 확정해제 check = [ 0 0 0 ]

 

: 각층마다 화살표 던지기 , check자리가 비어있는지 아닌지로 멈출지 말지 결정 

 

# 프린트실
def perm(depth):  # 각자 뎁스에서는? 
    if depth == 3:  # 최고 뎁스에 도달했으면? # if depth == len(sel)
        print(sel)  # print
        return

#화살표 던지기

    for i in range(3):  # 3번의 화살표 떨어트릴 기회
        if not check[i]:  # 각 기회 안에서 check를 보고 멈출 수 있는지 보고?
            check[i] = 1  # 멈출 수 있다면 if 통과했으니까 자리 차지했다고 표시하고
            sel[depth] = arr[i]  # 화살표가 떨어진 위치의 재료리스트
            perm(depth+1)
            check[i] = 0  # 돌아나오면서 다시 다음을 위해 초기화!! (중요)

# 확정 해제
check[i] = 0  # 돌아나오면서 다시 다음을 위해 초기화!! (중요)

 

각 층마다 화살표 3번 떨어뜨리는 기회를 가지는데, 멈추는 것은 그 열의 check가 비어있는지의 여부 (확정)

check가 차있으면 다음 자리로 가게 한 다음 , 확정한다 (check)

 

---

재귀조합

# 5C3
arr = ['A', 'B', 'C', 'D', 'E']
sel = [0, 0, 0]


def combination(idx, sidx):
    if sidx == 3:  # sel 길이 범위를 벗어나면 sel이 확정됐다는 소리니까 print
        print(sel)
        return

    if idx == 5:  # 얘도 벗어나지 않아야 함
        return

    sel[sidx] = arr[idx]  # sidx가 가리키는 위치에 idx가 가리키는 재료를 넣음
    combination(idx+1, sidx+1)  # 첫번째로는 두개의 화살표가 동시에 오른쪽으로 가보고
    combination(idx+1, sidx)  # 두번째로는 arr 쪽 화살표만 혼자 가봄.


combination(0, 0)

 

idx가 가르키는 애를 sel 안에 넣어라 

 

길이가 벗어나지 않은 경우,

3가지 로직만 존재

1. idx가 가리키는 애를 sel 이 가리키는 곳에 넣기

2. 둘다 같이 가기 

3. idx 혼자가기 

 

프린트실은 길이가 벗어난 경우 찍힘 sel = [A, B, C]

 

 

 

#프린트실

def combination(idx, sidx):
    if sidx == 3:  # sel 길이 범위를 벗어나면 sel이 확정됐다는 소리니까 print
        print(sel)
        return

    if idx == 5:  # 얘도 벗어나지 않아야 함
        return