순열

순열(permutation)

주어진 문자열에 대한 가능한 모든 조합, 즉 순열을 출력하는 방법을 알아본다.

 

재귀함수를 이용해 순열을 출력하는 방법

data = list("abc")

def permute(data, left, right):
    """
    data: character list
    return the permutation of the given string 
    """
    if left == right:
        print("".join(data))
    else:
        for i in range(left, right+1):
            data[left], data[i] = data[i], data[left]
            permute(data, left+1, right)
            data[left], data[i] = data[i], data[left] # backtrack


permute(data, 0, len(data)-1)

 

abc
acb
bac
bca
cba
cab

 

반복문을 이용해 순열을 출력하는 방법

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

 

힙의 알고리즘(Heap's algorithm)

힙소트와는 다름

def permute_heap(a, size):
    if size == 1:
        print(a)
        return
    
    for i in range(size):
        permute_heap(a, size-1)
        if size & 1:
            a[0], a[size-1] = a[size-1], a[0]
        else:
            a[i], a[size-1] = a[size-1], a[i]

 

python itertools을 이용할 수도 있다.

https://docs.python.org/3/library/itertools.html#itertools.permutations