[Algorithm] 순열(Permutation)이란? (feat.Swift)

 

안녕하세요 Foma 👟 입니다!

 

오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "순열"에 대해서 알아보도록 하겠습니다.

 

바로 시작할게요!

---

순열이란?

 

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 이른다. - 나무 위키 -

 

쉽게 설명하면 줄 세우기와 똑같아요.

 

A,B,C라는 학생을 줄 세우는 방법은 ABC,ACB,BAC,BCA,CAB,CBA 등이 있겠죠?

 

이 중에서 2명의 학생으로 줄 세우는 방법은 AB,AC,BA,BC,CA,CB 등이 있을거에요.

---

코드 구현

 

경우의 수들을 담을 이중 배열을 만들어줍니다.

 

var cases:[[Int]] = []

 

몇 개를 뽑을지 정해줍니다.

 

let pickCount = 3

 

본격적으로 순열 함수를 만들어줍니다.

 

파라미터로는

 

전체 인덱스가 담긴 numbers

 

현재 인덱스를 나타낼 current

 

몇개를 뽑아야 할지를 정할 pickCount

 

방문여부를 나타낼 visited

 

뽑은 인덱스를 담을 picked 로 설정해줍니다.

 

func permutaion(indexes:[Int],current:Int,pickCount:Int,visited:[Bool],picked:[Int]) {...}

 

그리곤 초기 방문이 비어있다면 인덱스의 갯수만큼 초기 방문을 설정해줍니다.

 

let initialVisited = visited.isEmpty ? Array(repeating: false, count: indexes.count) : visited

 

만약 현재 인덱스가 pickCount라면 cases에 담고 return 해줍니다.

 

 if current == pickCount {
        cases.append(picked)
        return
    }

 

만약 인덱스가 pickCount 전이라면

 

indexes를 순회하며 방문했는지 여부를 확인해서

 

방문하지 않았다면 방문을 체크하고 새로운 인덱스를 넣고 현재 인덱스에 + 1 해주고

 

재귀하여 줍니다.

 

 indexes
        .enumerated()
        .forEach{
            if !initialVisited[$0.offset] {
                var newVisited = initialVisited
                newVisited[$0.offset] = true
                var newPicked = picked
                newPicked.append($0.element)
                permutaion(indexes: indexes, current: current+1, pickCount: pickCount,visited: newVisited,picked: newPicked)
            }
        }

 

아래와 같이 원하는 조건을 넣고 경우의 수들을 출력해보면 모든 경우의 수가 담긴 것을 볼 수 있습니다.

 

permutaion(indexes: [1,2,3], current: 0,pickCount: 2,visited:[],picked: [])
print(cases)

//[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

---

전체 소스 코드