파이썬으로 순열 구현하기

1. 재귀적

# 재귀적으로 만들기
def perm(arr, depth, n, k):
    # depth가 0부터 시작하여 k라면 k개를 모두 뽑은 것이므로 print하고 return
    if (depth == k):
        print(arr)
        return
    for idx in range(depth, n):
        # 각 depth에 대해 남아 있는 것들 중에 모두 뽑아보고,
        # 해당 경우에 대해 재귀적으로 perm 함수를 돌리고,
        # 원상복구 하여 다시 경우의 수를 찾는다
        arr[idx], arr[depth] = arr[depth], arr[idx]
        perm(arr, depth+1, n, k)
        arr[idx], arr[depth] = arr[depth], arr[idx]

참고 : 순열(PERMUTATION) 알고리즘

 

2. linear하게 짜기

def permute(arr):
    result = [arr[:]]
    c = [0] * len(arr)
    i = 0
    while i < len(arr):
        if c[i] < i:
            if i % 2 == 0:
                arr[0], arr[i] = arr[i], arr[0]
            else:
                arr[c[i]], arr[i] = arr[i], arr[c[i]]
            result.append(arr[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

https://programmers.co.kr/learn/courses/4008/lessons/12836#note

 

3. 숫자로만 이루어진 리스트의 경우, 대소를 비교해가며 가장 작은 조합부터 가장 큰 조합까지 만들기

찾다보니 이런 것도 있었는데, 이 해결법의 경우 숫자로 이루어진 리스트에만 적용될 수 있다는 단점이 있지만 리니어하고, 훨씬 빠르다.

https://codepractice.tistory.com/59

(파이썬) 순열 -모든 경우 나열하기

4. 파이썬 공식 문서의 itertools > permutation 구현

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

generator로 반환하기 때문에 list 등으로 저장하고 싶다면 list(map(' '.join, permutations(pools))) 과 같이 써야 한다.