λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Programming/Algorithm

[Algorithm] μž¬κ·€λ₯Ό ν†΅ν•œ μˆœμ—΄(permutation) κ΅¬ν˜„(+ python λ‚΄μž₯ ν•¨μˆ˜ 이용)

728x90
λ°˜μ‘ν˜•

μˆœμ—΄μ΄λž€, N개의 μ›μ†Œμ—μ„œ μ›ν•˜λŠ” 개수λ₯Ό 뽑을 λ•Œ, μˆœμ„œκΉŒμ§€ κ³ λ €ν•˜λŠ” 것을 λ§ν•©λ‹ˆλ‹€.

 

μ˜ˆμ‹œ)

[1, 2, 3] λ°°μ—΄μ—μ„œ 2개의 μ›μ†Œλ₯Ό 선택할 경우

=> (1, 2), (1, 3), (2, 3), (2, 1), (2, 3), (3, 1), (3, 2)

μœ„μ™€ 같은 결과처럼 (1, 2), (2, 1)의 κ²½μš°λŠ” μ„œλ‘œ λ‹€λ₯Έ κ²ƒμœΌλ‘œ νŒλ‹¨ν•©λ‹ˆλ‹€.

πŸ₯Έ μž¬κ·€λ₯Ό ν†΅ν•œ μ½”λ“œ κ΅¬ν˜„

test = [1, 2, 3]
test_len = len(test)

N = 2   # 뽑을 μˆœμ—΄μ˜ 개수
visit = [0] * test_len # ν•΄λ‹Ή index의 값을 μ‚¬μš©ν–ˆλŠ”μ§€ μ—¬λΆ€
arr = [0] * N   # ν˜„μž¬ μˆœμ—΄μ„ 담을 λ°°μ—΄
arr_list = []   # λͺ¨λ“  μˆœμ—΄μ„ 담을 λ°°μ—΄

def permutaion(level):
    if level >= N:	# 레벨이 Nκ³Ό 같은 경우(이미 N개의 μ›μ†Œλ₯Ό μ„ νƒν•œ 경우)
        arr_list.append(arr[:]) # 얕은 볡사λ₯Ό ν†΅ν•΄μ„œ ν˜„μž¬ μˆœμ—΄μ„ μΆ”κ°€ν•œλ‹€.
        return
    else:
        for i in range(test_len):
            if visit[i]: continue   # 이미 μˆœμ—΄λ‘œ μ„ νƒλ˜μ—ˆλ‹€λ©΄ 톡과
            visit[i] = 1	# 아직 μ„ νƒλ˜μ§€ μ•Šμ€ κ²½μš°μ΄λ―€λ‘œ μ„ νƒμ²˜λ¦¬
            arr[level] = test[i]    # μˆœμ—΄μ„ 선택
            permutaion(level + 1)   # μž¬κ·€λ₯Ό 톡해 반볡
            visit[i] = 0    # λ‹€μŒ 트리둜 λ‚΄λ €κ°€κΈ° μœ„ν•΄μ„œ μ΄μ „μ˜ 방문처리λ₯Ό λ‘€λ°±

permutaion(0)	# 0개의 μ›μ†Œλ₯Ό μ„ νƒν•œ κ²½μš°λΆ€ν„° μ‹œμž‘
print(arr_list)

# μ‹€ν–‰κ²°κ³Ό
>>> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

파이썬의 경우 λ‚΄μž₯ν•¨μˆ˜λ₯Ό ν†΅ν•΄μ„œ 더 μ‰½κ²Œ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

πŸ₯Έ 파이썬 λ‚΄μž₯ν•¨μˆ˜ itertools.permutation을 ν†΅ν•œ κ΅¬ν˜„

import itertools

test = [1, 2, 3]
new_per = list(itertools.permutations(test, 2))	# test λ°°μ—΄μ—μ„œ 2개의 μ›μ†Œλ₯Ό λ½‘μ•„μ„œ μˆ˜μ—΄ 생성 ν›„ 리슀트둜 λ³€ν™˜
print(new_per)

# μ‹€ν–‰κ²°κ³Ό
>>> [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
728x90
λ°˜μ‘ν˜•