[Python] 완전 탐색 알고리즘 - 순열

순열(Permutations)

개념

n개 중에서 r개를 뽑아서 나열하는 경우의 수

서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관없이 r개의 원소를 선택하는 것

• ex)
  
  input : [1, 2, 3]
  output : [ [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] ]

---

코드

Git - 코드

방법 0 - 라이브러리 사용

from itertools import permutations

arr=[1,2,3]
print(list(permutations(arr,3)))

---

방법 1 - 알고리즘

def permutation(arr, r):
    # 1.
    arr = sorted(arr) # 정렬
    used = [0 for _ in range(len(arr))]
    # print(used)

    def generate(chosen, used):
        # 2.
        if len(chosen) == r:
            print(chosen)
            return
	
	# 3.
        for i in range(len(arr)):
            # print(i)
            if not used[i]:
                # print(i)
                # print(used)
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()
    generate([], used)

arr = [1, 2]
print(permutation(arr, 2))

1. 먼저 사용자가 원하는 arr 과 r 을 받는다. 그리고 arr 을 오름차순 정렬하는데 여기서는 큰 의미가 있지는 않고 단순히 출력을 이쁘게 하기 위해서이다. 그리고 used 변수를 만드는데, 이 변수는 i 번째 값을 썼는지 저장하는 데 쓰인다. 우리는 모든 순열을 하나씩 만들고 출력하는데 당연히 중복값은 저장되어서는 안 된다.
2. 실제 순열을 만들 generate 함수를 생성한다. 먼저 chosen 변수는 순열의 원소를 저장되는 변수인데 이 배열에 값을 하나씩 추가하다가 그 개수가 r 이 되는 순간 하나의 순열이 만들어진 것이므로 출력 후 종료한다.
3. 이 함수의 핵심이다. 모든 순열은 arr 의 0부터 i-1 번째 값으로 시작하기에 for 문으로 다 만들어야 한다. 그리고 chosen 에 값 추가 후, used 에 해당 변수를 사용했다고 체크한다. 그 다음 다시 generate 를 반복한다. 하나가 만들어진 후에는 그 값을 uncheck해줘야 한다.

출처

방법 1 - 과정

---

방법 2 - 알고리즘

def gen_permutations(arr, n):
    result=[]

    if n==0:
        return [[]]

    for i, val in enumerate(arr):
        for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
            result +=[[val]+P]

    return result


arr =[1, 2, 3]
print(gen_permutations(arr, 2))

출처

방법 2 - 과정